6.三数之和

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例 1：

1
2
3
4
5
6
7
8
输入：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：

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

示例 3：

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

提示：

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

题目思路

视频讲解：https://www.bilibili.com/video/BV1rv4y1H7o6/?p=178

双指针

这道题目使用双指针法 要比哈希法高效一些，那么来讲解一下具体实现的思路。

动画效果如下：

三数之和

拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。（相当于三个指针）

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于a = nums[i]，b = nums[left]，c = nums[right]。

接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

去重逻辑的思考

a的去重

说到去重，其实主要考虑三个数的去重。 a, b ,c, 对应的就是 nums[i]，nums[left]，nums[right]

a 如果重复了怎么办，a是nums里遍历的元素，那么应该直接跳过去。

但这里有一个问题，是判断 nums[i] 与 nums[i + 1]是否相同，还是判断 nums[i] 与 nums[i-1] 是否相同。

有同学可能想，这不都一样吗。

其实不一样！

都是和 nums[i]进行比较，是比较它的前一个，还是比较它的后一个。

如果我们的写法是 这样：

1
2
3
if (nums[i] == nums[i + 1]) { // 去重操作
    continue;
}

那我们就把 三元组中出现重复元素的情况直接pass掉了。 例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断 下一个也是-1，那这组数据就pass了。

我们要做的是 不能有重复的三元组，但三元组内的元素是可以重复的！

所以这里是有两个重复的维度。

那么应该这么写：

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

这么写就是当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。

这是一个非常细节的思考过程。

b与c的去重

很多同学写本题的时候，去重的逻辑多加了 对right 和left 的去重：（代码中注释部分）

1
2
3
4
5
6
7
8
9
10
11
12
while (right > left) {
    if (nums[i] + nums[left] + nums[right] > 0) {
        right--;
        // 去重 right
        while (left < right && nums[right] == nums[right + 1]) right--;
    } else if (nums[i] + nums[left] + nums[right] < 0) {
        left++;
        // 去重 left
        while (left < right && nums[left] == nums[left - 1]) left++;
    } else {
    }
}

但细想一下，这种去重其实对提升程序运行效率是没有帮助的。

拿right去重为例，即使不加这个去重逻辑，依然根据 while (right > left) 和 if (nums[i] + nums[left] + nums[right] > 0) 去完成right– 的操作。

多加了 while (left < right && nums[right] == nums[right + 1]) right--; 这一行代码，其实就是把 需要执行的逻辑提前执行了，但并没有减少 判断的逻辑。

最直白的思考过程，就是right还是一个数一个数的减下去的，所以在哪里减的都是一样的。

所以这种去重 是可以不加的。 仅仅是 把去重的逻辑提前了而已

而真正去重b和c的代码应该放在找到一个三元组之后，对b 和 c去重，并且去重后需要对left和right同时收缩

题解代码

三指针

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
/**
     * 三指针
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        // 先排序
        Arrays.sort(nums);
        // 排序后数组的第一个值如果大于0，则三数之和后一定不可能有等于0的情况，直接返回
        if (nums[0] > 0) {
            return res;
        }
    /*
        使用i指针固定一个值a,使用left指针固定一个值b，使用right指针固定一个值c
        指针 i 的取值范围 [0,nums.length-3],因为后面最少还需要留两个位置给right和left
     */
        for (int i = 0; i < nums.length - 2; i++) {
            // 对a进行去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int right = nums.length - 1;
            int left = i + 1;
            while (left < right) {
                // 三数之和
                int sum = nums[i] + nums[left] + nums[right];
                // 如果三数之和大于0，则需要将right--，反之将left++
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else { // 找到第一个三数和为0，加入结果集合后对数字b和c进行去重
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    // 找到答案时，双指针同时收缩
                    left++;
                    right--;
                }
            }
        }
        return res;
    }

回溯

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// 回溯算法，可同时解决四数之和等问题
public List<List<Integer>> threeSum3(int[] nums) {
       List<List<Integer>> result = new LinkedList<>();
       Arrays.sort(nums); // 排序
       dfs(3, 0, nums.length - 1, nums, 0, new LinkedList<>(), result);
       return result;
   }

   /**
    *
    * @param n 三数之和 n == 3  四数之和 n == 4
    * @param i 左边界
    * @param j 右边界
    * @param nums 数组
    * @param target 目标值
    * @param stack 栈 回溯用
    * @param result 结果集合 -> 存放最后的结果
    */
   public void dfs(int n, int i, int j, int[] nums, int target,
                   LinkedList<Integer> stack, List<List<Integer>> result) {
       if (n == 2) {
           // 如果n==2,走求解两数之和的逻辑
           towSum(nums, i, j, target, stack, result);
           return;
       }
       for (int k = i; k < j - (n - 2); k++) {
           if (k > i && nums[k] == nums[k - 1]) { // 去重
               continue;
           }
           int num = nums[k];
           stack.push(num); // 固定一个值
           dfs(n - 1, k + 1, j, nums, target - num, stack, result);
           stack.pop();
       }
   }

   /**
    * 两数之和
    * @param nums
    * @param i
    * @param j
    * @param target
    * @param stack
    * @param result
    */
   private void towSum(int[] nums, int i, int j, int target,
                       LinkedList<Integer> stack, List<List<Integer>> result) {

       while (i < j) {
           int sum = nums[i] + nums[j];
           if (sum < target) {
               i++;
           } else if (sum > target) {
               j--;
           } else {
               ArrayList<Integer> list = new ArrayList<>(stack);
               list.add(nums[i]);
               list.add(nums[j]);
               result.add(list);
               while (i < j && nums[i] == nums[i - 1]) { // 去重
                   i++;
               }
               while (i < j && nums[j] == nums[j + 1]) { // 去重
                   j--;
               }
               i++;
               j--;
           }
       }
   }

代码随想录：https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html
黑马满一航老师的数据结构「重点讲了回溯实现」：https://www.bilibili.com/video/BV1rv4y1H7o6/?p=178

hot100算法
#算法 #刷题
6.三数之和
http://example.com/2025/01/15/006-三数之和/
作者
Ovo-
发布于
2025年1月15日
许可协议