15. 三数之和

【饿了么、美团】外卖红包领取地址 >> 能省一点是一点

题目：https://leetcode-cn.com/problems/3sum/submissions/

代码：

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

思路：
1、先将数组按照从小到大进行排序，然后遍历数组，用i做索引。
2、对nums[i]进行判断，如果大于0则退出循环。原因：数组是从小到大排列的，如果第一个数都大于0，那么后面的数是大于第一个数的，所以无论如何sum值都不会为0。
3、在遍历nums[i]的时候，设置双指针，一个l一个r，分别从i后面的剩余元素一个左边一个右边进行遍历。在sum值小于0的时候，证明l索引所在的值太小了，需要变大一点即l++；在sum值大于0的时候，证明r索引所在的值太大了，需要变小一点，即r--。
4、经过以上3个条件已经可以得出结果了，但是在某些情况下结果会重复，所以需要进行去重优化，即代码中的第一层for循环中的if语句以及sum=0时的2个while语句。作用都一样。就是判断当前元素是否更上一个元素一样。一样的话得出的结果肯定是重复值，则可以直接跳过。

注意：
1、在去重这里花费的时间比较多。可以好好考虑一下。
2、在找到sum=0的时候，需要将3个元素添加到一个list中，然后再添加到res中，这里可以直接用Arrays.asList()方法做处理。省去自己new一个list然后挨个add的麻烦。