3SUM

Question

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.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Analysis

First, sort the array so that we can use binary search.

After pick up the first element in the triplets, use binary search approach to find the remaining two elements.

Pay attention to duplicate cases.

Solution

public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        if(nums==null||nums.length==0) return result;
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++){
            if(i==0||(i>0&&nums[i]!=nums[i-1])){
                int sum=0-nums[i];
                int l=i+1, r=nums.length-1;
                while(l<r){
                    if(nums[l]+nums[r]==sum){
                        result.add(Arrays.asList(nums[i],nums[l],nums[r]));
                        l++;
                        r--;
                        while(l<r&&nums[l]==nums[l-1]) l++;
                        while(r>l&&nums[r]==nums[r+1]) r--;
                    }else   if(nums[l]+nums[r]<sum) l++;
                            else                    r--;
                }
            }
        }
        return result;
    }