Finding all unique triplets that sums to zero (3Sum)

Given an array $S$ of $n$ integers, are there elements $a, b, c$ in $S$ such that $a + b + c = 0$? Find all unique triplets in the array which gives the sum of zero.
Note:

• Elements in a triplet $(a,b,c)$ must be in non-descending order. (i.e., $a \leq b \leq c$)
• The solution set must not contain duplicate triplets.

INPUT: $S$ = {-1, 0, 1, 2, -1, -4}
OUTPUT: (-1, 0, 1) and (-1, -1, 2)

Thoughts:
Apparently a $O(n^{3})$ algorithm exists but we can ignore it. To do better than that, we notice that if we can afford $O(n^{3})$, we can first sort $S$ in $O(n\log n)$. Does sorting help us in any way? The answer is definitely yes because it points out the direction of search for us. We can have a $O(n^{2})$ algorithm:
At outer loop, we iterate through every position from 0 to $n-1$. For a particular position $i$, we look at all the element between $S[i+1]$ to $S[n-1]$ (remeber that they are all sorted). We initialize two pointers $j = i+1$ and $k = n-1$. In the inner loop, we compute the sum $s = a[i]+ a[j]+ a[k]$. If s is bigger than 0, then we know we need to find something smaller, we decrease $k$. If s is smaller than 0, then we know we need to find something bigger, so we increase $j$. If the sum is exactly 0, we mark the triplet down and put it into the solution set (in order to find all of the solutions, we need to decrease $k$ and increase $j$ at the same time for this case). We continue this process until $j$ exceeds $k$. Therefore, the worst case for inner loop is to look at everything between $S[i+1]$ to $S[n-1]$. But each time we increase $i$ by 1 at outer loop, we have 1 less element needed to look at inner loop. Explicitly, the overall running time is given by $(n-1) + (n-2) + ... + 1 \equiv O(n^{2})$.

Code (Java):

public class Solution {
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
ArrayList<ArrayList<Integer>> result =
new ArrayList<ArrayList<Integer>>();
Arrays.sort(num);
for(int i = 0; i < num.length; ++i) {
int j = i + 1;
int k = num.length - 1;
while (j < k) {
int sum = num[i] + num[j] + num[k];
if(sum == 0) {
ArrayList<Integer> triplet =
new ArrayList<Integer>();
if(!result.contains(triplet))
j++;
k--;
} else if(sum > 0) {
k--;
} else { // sum < 0
j++;
}
}
}
return result;
}
}

Code (C++):
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int> > solution;
sort(num.begin(), num.end());
for(int i = 0; i < num.size(); ++i) {
int j = i + 1;
int k = num.size() - 1;
while (j < k) {
int sum = num[i] + num[j] + num[k];
if(sum == 0) {
vector<int> triplet(3);
triplet[0] = num[i];
triplet[1] = num[j];
triplet[2] = num[k];
if(find(solution.begin(), solution.end(),
triplet) == solution.end())
solution.push_back(triplet);
j++;
k--;
} else if(sum > 0) {
k--;
} else { // sum < 0
j++;
}
}
}
return solution;
}
};

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2dea09c0058', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2dea09c0086',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2dea09c0089',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Related