「刷刷刷」15.三数之和

发表于 更新于 分类于

题目

难度：中等

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum

思路

审题：最重要的一点是：不能重复。如果只是简单的三重循环去枚举所有可能，无法很好地解决不重复的问题。

那么有一个比较巧的办法是，先给数组排个序，再进行三重循环，每一重遍历的值都比上一重大，就可以避免这个问题。也就是找到的三元组：(a, b, c)，一定是满足 a <= b <= c的，不会出现 (b, a, c)，(b, c, a) 这种重复的情况。

既然数组已经是有序的了，还可以这样优化：第一层循环从小往大遍历，在每一次循环内，先取循环到的数字a，比a大的下一个数字b，和最后一个数字c。

  • 如果 a + b + c < 0，则说明整体偏小，应该让c不动，b变大一点，也就是指向后一位数字。
  • 如果 a + b + c > 0，则说明整体偏大，应该让b不动，c变小一点，也就是指向前一位数字。
  • 在这个过程中如果找到等于0的情况，则说明这一次a值的循环找到了答案，去遍历下一个a。如果b和c相遇了还没找到等于0，那说明这个a值没有答案，也去遍历下一个a。
    需要注意的是要跳过相等的元素，否则会有重复结果。

也就是说，先对数组排序。
然后遍历数组，固定一位数字a，一个指针B指向a下一位，一个指针C指向末尾元素。
判断 a + b + c ? 0，如果小于0，指针B右移；如果大于0，指针C左移。
注意指针移动时跳过相等的数字。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
    
        List<List<Integer>> res = new ArrayList<>();

       //  边界情况
        if (nums.length < 3) {
            return res;
        }
        
        // 排序
        Arrays.sort(nums);

        // 第一个元素已经 >0 的话，那么是找不到结果的
        if (nums[0] > 0) {
            return res;
        }

        // 外层循环，注意 i 的范围
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 左右两个指针
            int l = i + 1, r = nums.length - 1;

           // 内层循环
            while (l < r) {
                int temp = nums[i] + nums[l] + nums[r];
                if (temp < 0) {
                    l++;
                } else if (temp > 0) {
                    r--;
                } else {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    
                    // 注意这里跳过相同的元素
                    l++;
                    while (l < r && nums[l] == nums[l - 1]) {
                        l++;
                    }
                    r--;
                    while (l < r && nums[r] == nums[r + 1]) {
                        r--;
                    }
                }
            }
        }
        return res;
    }
}

作者：prik
永久链接： https://trzoey.github.io/blog-prik/algorithmic/15.三数之和/
转载请注明出处，谢谢合作💓。