Solution to LeetCode 3Sum problem.
Naive way is \(O(n^3)\) – look at all triplets. We can improve this to \(O(n^2)\) by first sorting the array, and traversing it with three pointers \(0 \leq i \lt j \lt k \lt N\). For every choice of \(i\), use the 2SUM algorithm on the sorted subarray, and find \(j\),\(k\) such that \(A(j) + A(k) = C - A(i)\), where in this question variant \(C = 0\). We must take care to not print duplicate elements.
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
Arrays.sort(num);
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < num.length-2; i++){
int j = i+1;
int k = num.length-1;
while(j < k){
int sum = num[i] + num[j] + num[k];
if(sum < 0) j++;
else if(sum == 0){
// If the sum is zero, have to skip over equal values
// for num[j] and num[k] so that we don't get duplicates
Integer[] arr = new Integer[]{num[i],num[j],num[k]};
result.add(new ArrayList<Integer>(Arrays.asList(arr)));
do{ j++; } while (j < k && num[j] == num[j-1]);
do{ k--; } while (j < k && num[k] == num[k+1]);
}
else k--;
}
// Move ahead the first tuple element so that we don't
// try another 3-tuple with the same first element.
while(i < num.length-1 && num[i] == num[i+1]) i++;
}
return result;
}