Question

link

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. (ie, a ≤ b ≤ c)
  • The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Stats

Frequency 5
Diffficulty 3
Adjusted Difficulty 5
Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

First of all, the array must be sorted first.

This question is solved with O(n^2) time. The idea is, for every integer, try to find a 2-integer pair so that the 3 numbers sum to 0. The method to use is 2-pointer scan.

Solution

Very important point of this question: there might be duplications in the result.

Eg. array = {-5, 2, 2, 3, 3}. When a = -5, we can choose 2, 3 and move pointers both by 1 position. Then we can choose 2, 3 again!

Solution is to increase the pointer to where the value is different. Pay special attention in writing the code. Because there are 3 parts that need duplication avoidance:

  1. The pivot number that we select, must be distinct each time. Why? because this is the smallest of the triplet. It must not be same.

  2. The left pointer and right pointer. They should point to a new value each time.

  3. Note that when sum is too large, move left pointer, and vice versa. However when sum is == 0, we move both left and right pointer.

Point 3 is the reason why we have 2 conditions in seperate if-block:

if (sum >= 0) {...}

if (sum <= 0) {...}

My code

public class Solution {
    public List<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (num == null || num.length < 3) {
            return ans;
        }
        Arrays.sort(num);
        int len = num.length;
        int left, right;
        for (int i = 0; i < len; i++) {
            // duplication avoidance 1
            if (i != 0 && num[i] == num[i - 1]) {
                continue;
            }
            left = i + 1;
            right = len - 1;
            while (left < right) {
                int sum = num[i] + num[left] + num[right];
                if (sum == 0) {
                    // now one triplet is found, add it to ans list
                    List<Integer> triplet = new ArrayList<Integer>();
                    triplet.add(num[i]);
                    triplet.add(num[left]);
                    triplet.add(num[right]);
                    ans.add(triplet);
                }
                // shrink the range between left and right pointer
                // (until the 2 pointers met)
                if (sum >= 0) {
                    // move right pointer to the left
                    right--;
                    // duplication avoidance 2
                    while (right >= 0 && num[right] == num[right + 1]) {
                        right--;
                    }
                }
                if (sum <= 0) {
                    // move left pointer to the right
                    left++;
                    // duplication avoidance 3
                    while (left < len && num[left] == num[left - 1]) {
                        left++;
                    }
                }
            }
        }
        return ans;
    }
}