Two Sum
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.
Constraints:
- 2 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- Only one valid answer exists
Examples:
Input: [2, 7, 11, 15] and target = 9
Output: [0, 1]
Explanation: Because nums[0] + nums[1] == 2 + 7 == 9, we return [0, 1].
Solutions
Hash Table Approach
We use a hash table to store the numbers we have seen so far and their indices. For each number, we check if its complement (target - number) is in the hash table. If it is, we return the indices of the complement and the current number. If not, we add the current number and its index to the hash table.
def twoSum(nums, target):
num_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_map:
return [num_map[complement], i]
num_map[num] = iFollow-up:
What if we cannot use the same element twice, but there are multiple pairs that add up to the target?
