Problem Name: Two Sum
Problem Statement:
Given an array of integers `nums` and an integer `target`, return indices of the two numbers such that they add up to `target`. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
Input:
An array of integers `nums` (1 ≤ nums.length ≤ 10^4, -10^9 ≤ nums[i] ≤ 10^9).
An integer `target` (-10^9 ≤ target ≤ 10^9).
Output:
Indices of the two numbers such that they add up to `target`.
Constraints:
Only one valid answer exists.
Each element in the array is unique.
Example:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Platforms:
Companies:
- Microsoft
Topics Covered:
Hash Tables,
Array
Solution:
Algorithm:
1. Create a hash table to store the complement of each number.
2. Iterate through the array.
3. For each number, check if its complement exists in the hash table.
4. If found, return the indices.
5. Otherwise, add the number and its index to the hash table.
Code Implementation:
C:
#include <stdio.h> #include <stdlib.h> int* twoSum(int* nums, int numsSize, int target, int* returnSize){ int* result = (int*)malloc(2 * sizeof(int)); for (int i = 0; i < numsSize; i++) { for (int j = i + 1; j < numsSize; j++) { if (nums[i] + nums[j] == target) { result[0] = i; result[1] = j; *returnSize = 2; return result; } } } *returnSize = 0; return NULL; }
C++:
#include <vector> #include <unordered_map> using namespace std; vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int> numMap; for (int i = 0; i < nums.size(); i++) { int complement = target - nums[i]; if (numMap.find(complement) != numMap.end()) { return {numMap[complement], i}; } numMap[nums[i]] = i; } return {}; }
Java:
import java.util.HashMap; public class Solution { public int[] twoSum(int[] nums, int target) { HashMap<integer > map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } }
Python:
from typing import List class Solution: def two_sum(self, nums: List[int], target: int) -> List[int]: num_map = {} for i, num in enumerate(nums): complement = target - num if complement in num_map: return [num_map[complement], i] num_map[num] = i return []
Complexity Analysis:
Case | Time Complexity | Space Complexity |
---|---|---|
Worst Case | O(n) | O(n) |
Average Case | O(n) | O(n) |
Best Case | O(1) | O(n) |