Problem Description

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Solution

The problem has some similarities with LeetCode 1: Two Sum. The difference is here the solutions may be multiple. Therefore, we can borrow the same idea, at the same time take care of duplicate issues, which can be achieved by sorting the array first, since the time complexity of sorting is no larger than the total complexity of the problem.

Another thought is that given a sorted array, to find two elements summed to a target, we could use two pointers, which achieves an O(n) time complexity. That is, we put two pointers, one at the left with another one at the right. Next, we check the sum and compared to the target, and move left pointer to the right if the sum is less, or right pointer to the left if the sum is larger. Basically, at each step, we have two options of either increasing or decreasing the sum, instead of only increasing if we put both pointers at the left side.

Java Code

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort( nums );
        List<List<Integer>> ret = new ArrayList<>();
        int len = nums.length, p1 = 0;
        while( p1<len-2 ){
            int l=p1+1, r=len-1;
            while(l < r){
                int sum = nums[p1]+nums[l]+nums[r];
                if( sum == 0 ){
                    ret.add( Arrays.asList(nums[p1], nums[l], nums[r]) );
                    while( ++l<r && nums[l]==nums[l-1] ) ;
                    while( --r>l && nums[r]==nums[r+1] ) ;
                }
                else if( sum < 0 ) while( ++l<r && nums[l]==nums[l-1] ) ;
                else while( --r>l && nums[r]==nums[r+1] ) ;
            }
            while(++p1<len-2 && nums[p1]==nums[p1-1]) ;
        }
        return ret;
    }

}