每日n刷：leetcode15. 三数之和

每日n刷：leetcode15. 三数之和 15. 三数之和

双指针

双指针

关键点1：因为题目目标值为0，所以一定会出现几个数是非正数，利用这个性质，先固定一个值，然后去寻找两个值等于固定这个值的相反数就是所要的答案，利用双指针不断缩小范围另外两个数的范围即可求出答案。
关键点2：题中要求不能出现重复的答案，那么我们需要先保证数组有序，在答案符合要求之后，下一个即将判断的数不能与当前数一致。

class Solution {
    public List> threeSum(int[] nums) {
        ArrayList> res = new ArrayList>();
        int n = nums.length;
        // 特判
        if(n < 3) return res;
        Arrays.sort(nums);
        // -2 以减少不必要的判断次数
        for(int i = 0; i < n - 2; i ++) {
            // 下一个值与当前值相同需要跳过
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            // 当前值>0就不可能三数之和==0
            if(nums[i] > 0) break;
            // 双指针
            int l = i + 1;
            int r = n - 1;
            // 目标值
            int tar = -nums[i];
            while(l < r) {
                int tmp = nums[l] + nums[r];
                if(tmp < tar) {
                    l ++;
                }else if(tmp > tar) {
                    r --;
                }else {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    // 当前不是最后一个数(|| 第一个数) && 当前数与下一个判断的数相同
                    while(l < n - 1 && nums[l] == nums[l + 1]) l ++;
                    while(r > i + 1 && nums[r] == nums[r - 1]) r --;
                    l ++;
                    r --;
                }
            }
        }
        return res;
    }
}