Given an array of integers, are there elements in such that ? Find all unique triplets in the array which gives the sum of zero.

Note:

- Elements in a triplet must be in non-descending order. (i.e., )
- The solution set must not contain duplicate triplets.
INPUT: = {-1, 0, 1, 2, -1, -4}

OUTPUT: (-1, 0, 1) and (-1, -1, 2)

**Thoughts:**

Apparently a algorithm exists but we can ignore it. To do better than that, we notice that if we can afford , we can first sort in . 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 algorithm:

At outer loop, we iterate through every position from 0 to . For a particular position , we look at all the element between to (remeber that they are all sorted). We initialize two pointers and . In the inner loop, we compute the sum . If s is bigger than 0, then we know we need to find something smaller, we decrease . If s is smaller than 0, then we know we need to find something bigger, so we increase . 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 and increase at the same time for this case). We continue this process until exceeds . Therefore, the worst case for inner loop is to look at everything between to . But each time we increase by 1 at outer loop, we have 1 less element needed to look at inner loop. Explicitly, the overall running time is given by .

**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>(); triplet.add(num[i]); triplet.add(num[j]); triplet.add(num[k]); if(!result.contains(triplet)) result.add(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; } };Advertisements

## 2 Comments

(+add yours?)