3Sum

Problems

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: 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]
]

Solution

O(n^2)

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 3) return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < len - 2; i++) { //notice the bound of i
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break; //min is > 0, no way to get other res
            if (nums[i] + nums[len -1 ] + nums[len - 2] < 0) continue; //cur max is < 0, we continue the loop to get bigger 
            if (i != 0 && nums[i] == nums[i-1]) continue; //skip duplicates between i and its right 
            int low = i + 1, high = len - 1;
            while (low < high) {
                if (nums[i] + nums[low] + nums[high] < 0) low++;
                else if (nums[i] + nums[low] + nums[high] > 0) high--;
                else {
                    res.add(Arrays.asList(nums[i], nums[low], nums[high]));
                    while (low < high && nums[low] == nums[low + 1]) low++; //skip the duplicates between low and its right
                    while (low < high && nums[high] == nums[high - 1]) high--; //skip the duplicates between high and its left
                    low++;
                    high--; 
                }
            }
        }
        return res;
    }
}

Analysis

This solution uses two pointers and binary search to get the correct result
We first check some corner invalid cases and sort the given input
Then we loop from the start until the last three numbers, the sum will be increasing
If nums[i] + nums[i+1] + nums[i+2] (min) is smaller than target 0, we break
If nums[i] + nums[len - 1] + nums[len -2] (current max) is greater than target 0, we continue
We also need to check duplicates because the problems requires none duplicated elements in our result
After that, we use binary search to get our result
Notice that we use Arrays.asList() to construct a list conveniently