Question

link

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

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

Stats

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²) 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;
    }
}