Two Sum
Problem
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You can return the answer in any order.
nums = [2, 7, 11, 15], target = 9[0, 1]def two_sum(nums, target):
seen = {}
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
return Nonefunction twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) return [seen.get(need), i];
seen.set(nums[i], i);
}
return null;
}class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need)) return new int[]{ seen.get(need), i };
seen.put(nums[i], i);
}
return null;
}
}vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> seen;
for (int i = 0; i < (int)nums.size(); i++) {
int need = target - nums[i];
if (seen.count(need)) return { seen[need], i };
seen[nums[i]] = i;
}
return {};
}Explanation
The simple idea would be to try every pair of numbers and check if they add up to the target. That works, but it is slow because you re-check the same numbers again and again.
The trick here is to walk through the array once and remember every number we have already seen in a hash map (a quick lookup table of value → index).
For the current number x, the partner we need is need = target − x. If that partner is already in the map, we found our pair and return both indices. If not, we drop x into the map and move on.
Example: nums = [2, 7, 11, 15], target = 9. At 2 we need 7 — not seen yet, so store 2. At 7 we need 2 — it is in the map at index 0, so the answer is [0, 1].
Because the map gives instant lookups, we only pass through the list one time, which is why this is fast.