[LeetCode] 15. 3Sum

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)

public class Solution {
    public List> threeSum(int[] nums) {
        int len = nums.length;
        List> ret = new ArrayList>();
        Arrays.sort(nums);
        for(int i = 0; i < len; ++i){
            if(i > 0 && nums[i-1] == nums[i])
                continue;
            int x = i+1;
            int y = len-1;
            while(x < y){
                int sum = nums[x] + nums[y];
                sum += nums[i];
                if(0 == sum){
                    Integer[] res = {nums[x], nums[y], nums[i]};
                    Arrays.sort(res);
                    ret.add(Arrays.asList(res));
                    --y;
                    while(y >= 0 && nums[y+1] == nums[y]){
                        --y;
                    }
                    ++x;
                    while(x < len && nums[x-1] == nums[x]){
                        ++x;
                    }
                }else if(0 < sum){
                    --y;
                    while(y >= 0 && nums[y+1] == nums[y]){
                        --y;
                    }
                }else{
                    ++x;
                    while(x < len && nums[x-1] == nums[x]){
                        ++x;
                    }
                }
            }
        }
        
        return ret;
    }
}