Leetcode15. 三数之和 (排序+双指针优化解法)步骤详解

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

题目地址

Leetcode 15. 三数之和

解题思路

1.暴力三循环

  第一种方法也是我们能够快速想出来的方法，即使用三个指针i、j、k分别指向三个数，进行遍历，遍历完进行去重操作即可，这里不做过多赘述，主要以第二种方法为主。

2.固定指针+双循环指针

  我们使用一个固定指针k，指向数组的开头，使其不断自增，小于nums.length - 2，这里需要小于 nums.length - 2，是因为需要保证其指针后最少有一个i指针和j指针的存在。
  随后我们使i指针指向k指针的后面一个位置，j指针指向数组末尾。

  判断sum = nums[k] + nums[i] + nums[j] 三者的和：

• sum == 0:
    这时nums[k],nums[i],nums[j]三个数即为我们所求的三个数，将其插入返回链表中，并且使得i++和j–。

  这里需要说明一下的是，对两个指针的操作是同时的，简单说一下原因：
  在k不变的情况下，三者之和为0，那么当i++单独执行后，且不与之前的值重复，则更新后的三者必不可能为0，必大于0，此时则需要将 j–；
  反之，若仅仅更新j–，则三者之和必小于0，则下一步必然是更新i++。
  综上两种情况，无论我们怎么变化，都是需要同时变更两个指针，即该操作是需要将两者同时进行更新的，仅仅变更一个指针的话，在下一个循环内会变更另外一个指针，则会多循环一次。

• sum < 0:
  三者之和 < 0，则说明值太小了，需要将小一点的数变大，仅有i++可以实现。
• sum > 0:
  三者之和 > 0，则说明值太大了，需要将大一点的数变小，仅有j–可以实现。

代码示例

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new LinkedList<>();

        // 这里让k < nums.length - 2 ，是保证k在i和j之前。
        for (int k = 0; k < nums.length - 2; k++) {
            if (nums[k] > 0) {
                // 如果连最小的数都是 > 0 ，那么后面的数都是比他大的数，则相加之后必为一个 > 0 的数
                break;
            }

            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }

            int i = k + 1;
            int j = nums.length - 1;

            while (i < j) {
                // nums[i] == nums[i - 1]时，直接跳过即可，因为结果和nums[i - 1]一致
                if (i >= k + 2) {
                    if (nums[i] == nums[i - 1]) {
                        i++;
                        continue;
                    }
                }
                // nums[j] == nums[j + 1]时，直接跳过即可，因为结果和nums[j + 1]一致
                if (j < nums.length -1) {
                    if (nums[j] == nums[j + 1]) {
                        j--;
                        continue;
                    }
                }

                // 判断三者之和是否为0
                if (nums[k] + nums[i] + nums[j] == 0) {
                    List<Integer> list = new LinkedList<>();
                    list.add(nums[k]);
                    list.add(nums[i]);
                    list.add(nums[j]);

                    ret.add(list);
                    // 这里将i和j都进行更新
                    i++;
                    j--;
                } else if (nums[k] + nums[i] + nums[j] > 0) {
                    j--;
                } else {
                    i++;
                }
            }
        }
        return ret;
    }
}