Solution to the LeetCode Two Sum problem.
There is a number of ways to do this:
- Naive – explore all pairs of two – \(O(n^2)\)
- Sort and use two pointers – \(O(n\log{n})\)
- Use a hashmap – \(O(n)\), but requires some extra bookkeeping.
In this solution, I’ll use a hashmap, since I’ll use the sorting method for the later questions on Three-Sum and Four-Sum. The hashmap solution works as follows – add all the elements one by one to the hashmap. Then, traverse the array again, and for each element \(i\), check if \(c-i\) (where \(c\) is the desired sum) is in the hashmap. If so, we found a match. The issue is we need to keep track of the indices where each element appeared at, otherwise we’ll get false positives for cases such as \([5,2]\) and we are looking for a sum \(10\). The algorithm will say a solution exists, when it clearly doesn’t.
public class Solution {
public int[] twoSum(int[] numbers, int target) {
HashMap<Integer, Set<Integer>> hm = new HashMap<Integer, Set<Integer>>();
int[] result = new int[2];
for(int i = 0; i < numbers.length; i++){
int num = numbers[i];
if(!hm.containsKey(num)){
hm.put(num, new HashSet<Integer>());
}
hm.get(num).add(i);
}
for(int i = 0; i < numbers.length; i++){
int num = numbers[i];
if(hm.containsKey(target-num)){
Set<Integer> indices = hm.get(target-num);
if( !(indices.contains(i) && indices.size() == 1) ){
Integer[] ind = indices.toArray(new Integer[0]);
int j = 0;
for(int k : ind){
if(i != k){
j = k;
break;
}
}
result[0] = Math.min(j,i) + 1;
result[1] = Math.max(j,i) + 1;
return result;
}
}
}
return result;
}
}