3Sum

原题地址：https://leetcode.com/problems/3sum/#/description

题目：

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

解法：
这道题难点在于考虑一些边界条件。例如如何去重，i, j, k指针如何变动，arrays是不是sorted等。

代码：

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> rst = new ArrayList<>();
    if(nums == null || nums.length <= 2){
        return rst;
    }
    Arrays.sort(nums);
    for(int i = 0; i <= nums.length - 3; i++){
        while(i != 0 && nums[i - 1] == nums[i] && i <= nums.length - 3){
            i++;
        }
        int j = i + 1;
        int k = nums.length - 1;
        while(j < k){
            List<Integer> list = new ArrayList<>();
            int sum = nums[i] + nums[j] + nums[k];
            if(sum == 0){
                list.add(nums[i]);
                list.add(nums[j]);
                list.add(nums[k]);
                rst.add(list);
                j++;
                k--;
                while(j < k && nums[j - 1] == nums[j]){
                    j++;
                }
                while(j < k && nums[k + 1] == nums[k]){
                    k--;
                }
            }
            else if(sum < 0){
                j++;
            }
            else{
                k--;
            }
        }
    }
    return rst;
}