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.
Examples
nums = [2,7,11,15], target = 9
[0,1]
Because nums[0] + nums[1] == 9, we return [0, 1].
nums = [3,2,4], target = 6
[1,2]
Because nums[1] + nums[2] == 6, we return [1, 2].
Constraints
- •
2 <= nums.length <= 10^4 - •
-10^9 <= nums[i] <= 10^9 - •
-10^9 <= target <= 10^9 - •
Only one valid answer exists.
Approaches
Check every pair of numbers to see if they sum to target using nested loops.
def two_sum(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []Sort the array with indices preserved, then use two pointers from both ends.
def two_sum(nums, target):
sorted_nums = sorted(enumerate(nums), key=lambda x: x[1])
left, right = 0, len(nums) - 1
while left < right:
curr_sum = sorted_nums[left][1] + sorted_nums[right][1]
if curr_sum == target:
return [sorted_nums[left][0], sorted_nums[right][0]]
elif curr_sum < target:
left += 1
else:
right -= 1
return []Use a hash map to store complements. For each number, check if target - num exists in the map.
Diagram
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Check every pair of numbers to see if they sum to target using nested loops. |
| Sorting + Two Pointers | O(n log n) | O(n) | Sort the array with indices preserved, then use two pointers from both ends. |
| Hash Map | O(n) | O(n) | Use a hash map to store complements. For each number, check if target - num exists in the map. |
Check every pair of numbers to see if they sum to target using nested loops.
Sort the array with indices preserved, then use two pointers from both ends.
Use a hash map to store complements. For each number, check if target - num exists in the map.
Common Mistakes
Using the same element twice (need two different indices)
Not handling the case where no solution exists
Brute force checks pairs twice