3Sum

题目

Given an array S of n integers, are there elements a,b,c inS 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]
]

解析

问题一：为何不用

 List<Integer> currLevel = new ArrayList<>();
 currLevel.add(nums[i]);
 currLevel.add(nums[j]);
 currLevel.add(nums[k]);
 result.add(currLevel);

而要 result.add(Arrays.asList(nums[i],nums[j],nums[k])); ?

其实两者是等价的。 上者只能逐个元素加到list里，下者可以n个元素一次性加到list里

Arrays.asList的用法：“This method provides a convenient way to create a fixed-size list initialized to contain several elements”

 List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");

问题二： 为何查重会有if(i>0 && nums[i]==nums[i-1]) continue;和 while(j<k && nums[j]==nums[j-1]) j++;的形式？ 因为最外围for循环只能一次处理一个元素，怎只需要用if判断当前元素与前一个元素比较是否重复。 而while循环则没有该限制。

思路

1. two pointers
2. For each possible first element we make a standard bi-directional 2Sum sweep of the remaining part of the array
3. Meanwhile, we need to skip equal elements to avoid duplicates

图解

代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int target  = 0;
        Arrays.sort(nums);
        if(nums.length<3) return result;

        for(int i = 0; i< nums.length-2; i++){
            if(i>0 && nums[i]==nums[i-1]) continue;
            int j = i+1;
            int k = nums.length-1;
            while(j<k){
                if(nums[i] + nums[j]+nums[k] < target){
                    j++;
                    while(nums[j]==nums[j-1] && j<k) j++;
                }else if(nums[i]+nums[j]+nums[k]> target){
                    k--;
                    while(nums[k]==nums[k+1] && j<k)k--;
                }else{
                    result.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    j++;
                    while(nums[j]==nums[j-1]&& j<k) j++;
                }
            }
        }
        return result;
    }
}