Given an array of integers
nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution, and you may not use the same element twice. You can return the answer in any order.Example
nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Because nums[0] + nums[1] = 2 + 7 = 9.
As you iterate through the array, for each number check if (target - current number) already exists in a hashmap. If it does, you've found your pair. If not, store the current number and its index in the map for future lookups. This turns the brute-force O(n^2) search into a single O(n) pass.
Why this works
For each number, you need to find if its “partner” (target minus current) exists. Instead of scanning the whole array each time (O(n^2)), store every number you’ve seen in a hashmap. This lets you check for the partner in O(1).
Step by step
- Walk through the array — for each number, compute what value you’d need to reach the target.
- Check the hashmap — if that complement value has been seen before, you found your answer.
- Store and move on — if not found, record the current number and its index for future lookups.
Time: O(n)
Space: O(n)
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (seen.containsKey(complement)) { // found the pair
return new int[] {seen.get(complement), i};
}
seen.put(nums[i], i); // remember this number's index
}
return new int[] {};
}
}
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> seen;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (seen.count(complement)) { // found the pair
return {seen[complement], i};
}
seen[nums[i]] = i; // remember this number's index
}
return {};
}
};
def twoSum(nums: list[int], target: int) -> list[int]:
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen: # found the pair
return [seen[complement], i]
seen[num] = i # remember this number's index
return []