15. 三数之和

https://leetcode-cn.com/problems/3sum/

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resList = new ArrayList<>();
        if (nums == null || nums.length == 1 || nums.length == 2) {
            return resList;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break;
            if (i >= 1 && nums[i] == nums[i - 1]) continue;
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    resList.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 这里面也要变化
                    left++;
                    right--;
                    // 内部也要有重复的验证
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right+ 1]) right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return resList;
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resList = new ArrayList<>();
        // 特殊值判断
        if (nums == null || nums.length == 1 || nums.length == 2) {
            return resList;
        }
        // 先对nums进行排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            // i最多扩展到倒数第三位
            // 因为已经排过序，如果num[i]>0则必然无解。
            if (nums[i] > 0) {
                return resList;
            }
            // ！！！且如果当前值与下一个值相同，则会存在与之前一样的重复解，跳过这个，上一个解已经记录
            // i=0时必然无法与前一个数比较
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 当前元素记录下来
            int cur = nums[i];
            // 定义双指针L，R
            int L = i + 1, R = nums.length - 1;
            while (L < R) {
                // 在遍历中寻找有无合适的值
                int temp = cur + nums[L] + nums[R];
                // 如果temp值大于 0，说明 nums[R] 太大，R 左移。不可能是L右移，temp只会更大。
                // 如果temp值小于 0，说明 nums[L] 太大，L 左移。同理。
                if (temp == 0) {
                    // 这里需要讨论几点：去重+移动
                    // 临时list添加元素，并加入resList中
                    List<Integer> list = new ArrayList<>();
                    list.add(cur);
                    list.add(nums[L]);
                    list.add(nums[R]);
                    resList.add(list);
                    // 去重操作：判断左届或右界是否与相邻为重复，重复就需要跳过
                    while (L < R && nums[L] == nums[L + 1]) L++;
                    while (L < R && nums[R] == nums[R - 1]) R--;
                    // 否则正常向后遍历
                    L++;
                    R--;
                } else if (temp > 0) {
                    R--;
                } else if (temp < 0) {
                    L++;
                }
            }
        }
        return resList;
    }
}