[LeetCode Hot 100] LeetCode15. 三数之和

题目描述

思路

1. 特判：对于数组长度为n，如果数组为null或者数组长度小于3，返回[]。
2. 对数组进行排序。
3. 遍历排序后的数组：
   1. 若 nums[i]>0nums[i]>0nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 000，直接返回结果。
   2. 对于重复元素：跳过，避免出现重复解。
   3. 令左指针 L=i+1L=i+1L=i+1，右指针 R=n−1R=n-1R=n−1，当 L<RL<RL<R 时，执行循环：
      1. 当nums[i] + nums[L] + nums[R] == 0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将L，R移动到下一位置，寻找新的解。
      2. 若和大于0，说明nums[R]太大，R左移。
      3. 若和小于,0，说明nums[L]太小，L右移。

对撞双指针：有序。
定义i < j < k，其中固定nums[i]，把j和k当做双指针。

方法一：双指针

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 1. 特殊值判断
        int len = nums.length;
        if (nums == null || len < 3) return null;
        // 2. 结果集
        List<List<Integer>> res = new ArrayList<>();
        // 3. 对数组进行排序
        Arrays.sort(nums);
        for (int i = 0; i < len; i ++) {
            // 规定i < j < k, 若nums[i] > 0,则三数之和一定不会等于0
            if (nums[i] > 0) break;
            // 第一次去重:如果i和上一次相同,则会得到相同结果,因为每遍历一次i都会得出所有结果
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            // 定义双指针
            int j = i + 1;
            int k = len - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    // 第二次去重
                    while (j < k && nums[j] == nums[j + 1]) j ++;
                    while (j < k && nums[k] == nums[k - 1]) k --;
                    // while只是停止在了下一个不重复的地方。但是还没有移动那个下一个位置。 所以需要在进行一次++--
                    j ++;
                    k --;
                } else if (sum > 0) {
                    k --;
                } else if (sum < 0) {
                    j ++;
                }
            }
        }
        return res;
    }
}