Problem
Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.
You may assume each input has exactly one solution, and you may not use the same element twice.
Example
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Reason: nums[0] + nums[1] = 2 + 7 = 9Solution
The brute force approach uses two nested loops with O(n²) time. We can do better with a hash map: store each number we’ve seen along with its index, then for each new number, check if its complement (target – num) is already in the map.
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 []function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) {
return [seen.get(complement), i];
}
seen.set(nums[i], i);
}
return [];
}#include <vector>
#include <unordered_map>
using namespace std;
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)) {
return {seen[complement], i};
}
seen[nums[i]] = i;
}
return {};
}import java.util.HashMap;
import java.util.Map;
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)) {
return new int[]{seen.get(complement), i};
}
seen.put(nums[i], i);
}
return new int[]{};
}Complexity
- Time: O(n) — single pass through the array
- Space: O(n) — hash map stores up to n elements
Why This Works
The key insight is that for each number, we know what value we’d need to pair it with. Instead of searching the whole array (O(n)), we use a hash map for instant O(1) lookups. We iterate once, and at each step we check if the complement exists. If yes, we found our pair. If no, we add the current number to the map and move on.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?