Two Sum [Easy] — HashMap Complement Lookup
Sanjeev SharmaAdvertisement
Problem Statement
Given an array and target, return indices of the two numbers that add to target. Exactly one solution. May not use the same element twice.
Input: nums=[2,7,11,15], target=9 → Output: [0,1]
Input: nums=[3,2,4], target=6 → Output: [1,2]
Intuition
One-pass HashMap: for each element, check if target - element is already in the map. If yes, return both indices. If no, store element → index.
Solutions
C
int* twoSum(int* nums, int n, int target, int* retSize) {
// Use a hash table via sorted index pairs for bounded values
// Simplified: O(n^2) for unbounded; real: use hashmap library
int* res = malloc(2*sizeof(int)); *retSize=2;
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++)
if(nums[i]+nums[j]==target){res[0]=i;res[1]=j;return res;}
return res;
}
C++
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> mp;
for(int i=0;i<nums.size();i++){
int comp=target-nums[i];
if(mp.count(comp)) return {mp[comp],i};
mp[nums[i]]=i;
}
return {};
}
Java
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> mp=new HashMap<>();
for(int i=0;i<nums.length;i++){
int comp=target-nums[i];
if(mp.containsKey(comp)) return new int[]{mp.get(comp),i};
mp.put(nums[i],i);
}
return new int[]{};
}
JavaScript
var twoSum = function(nums, target) {
const mp=new Map();
for(let i=0;i<nums.length;i++){
const comp=target-nums[i];
if(mp.has(comp)) return [mp.get(comp),i];
mp.set(nums[i],i);
}
};
Python
def twoSum(nums: list[int], target: int) -> list[int]:
seen = {}
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target-x], i]
seen[x] = i
Complexity
- Time: O(n) — one pass
- Space: O(n) — map storage
Variants
- Two Sum II (sorted) → two pointers O(1) space
- Two Sum III (design) → HashMap + count
- Two Sum IV (BST) → HashSet BFS/DFS
Advertisement
