三数之和
字数 3274 2025-12-20 04:15:14

三数之和

题目描述

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

注意：

  1. 答案中不可以包含重复的三元组。
  2. 输入的数组长度 n 满足：3 <= n <= 3000。
  3. 数组元素的范围：-10^5 <= nums[i] <= 10^5。

示例：
输入：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，但 [-1, 0, 1] 和 [-1, -1, 2] 的组合都满足条件，且没有重复。

解题过程详解

核心思路

最直接的方法是三重循环枚举所有可能的 (a, b, c) 组合，检查其和是否为0，并去重。但这样做时间复杂度是 O(n³)，对于 n 最大为3000来说是不可接受的。我们需要一个更高效的策略。

核心优化思想：固定其中一个数，将三数之和问题转化为两数之和问题。

具体步骤如下：

  1. 排序数组：首先对数组进行排序（例如升序排序）。这是后续进行高效搜索和去重的基础。
  2. 枚举固定数：遍历排序后的数组，将当前遍历到的元素 nums[i] 作为我们想要固定的第一个数 a。
  3. 转化为两数之和问题：问题就变成了：在 nums[i] 之后的子数组中，寻找两个数 b 和 c，使得 b + c = -a（即 0 - nums[i]）。
  4. 高效寻找两数之和：对于已排序的数组，寻找和为特定目标值的两个数，可以使用 双指针法。初始化一个左指针 left 指向 i+1，右指针 right 指向数组末尾 n-1。计算 nums[left] + nums[right] 的和，与目标值 -nums[i] 比较：
    • 如果和 > 目标值，说明 nums[right] 太大了，将 right 左移一位。
    • 如果和 < 目标值，说明 nums[left] 太小了，将 left 右移一位。
    • 如果和 = 目标值，则找到一组解 (nums[i], nums[left], nums[right])。记录后，需要移动指针寻找其他可能的解，同时要跳过重复的元素以避免重复的三元组。
  5. 关键的去重：
    • 对于固定的第一个数 a (nums[i])，如果它和前一个固定的数相同（即 nums[i] == nums[i-1]），那么以它开头的所有三元组必定和以 nums[i-1] 开头的三元组重复。因此，我们可以跳过它，直接 continue。
    • 当找到一组解后，我们需要移动 left 和 right 指针。在移动时，如果下一个 left 指向的值与当前值相同，那么 (nums[i], nums[left+1], nums[right]) 这个三元组和刚找到的会是重复的。因此，我们需要一个 while 循环，将 left 一直移动到下一个不同的值。同理，对于 right 指针也需要一个向左移动的 while 循环来跳过重复值。
  6. 提前终止：由于数组已排序，如果固定的第一个数 nums[i] 已经大于0，那么它后面所有的数都大于0，三数之和不可能为0，可以直接结束整个循环。

详细步骤分解（以示例 nums = [-1, 0, 1, 2, -1, -4] 为例）

  1. 排序：

    • 排序后的数组为：nums = [-4, -1, -1, 0, 1, 2]

  2. 开始遍历，固定第一个数 a（下标 i）：

    • i = 0, a = nums[0] = -4。目标两数之和为 -a = 4。
    • 初始化双指针：left = i+1 = 1, right = 5。
    • 进入 while (left < right) 循环：
      • 计算 nums[left] + nums[right] = -1 + 2 = 1。1 < 4，和太小，left 右移。
      • left = 2, 和 = -1 + 2 = 1，仍然小于4，left 右移。
      • left = 3, 和 = 0 + 2 = 2，小于4，left 右移。
      • left = 4, 和 = 1 + 2 = 3，小于4，left 右移。
      • left = 5，此时 left 不再小于 right，循环结束。未找到和为4的组合。
    • i 移动到下一位。

  3. i = 1, a = nums[1] = -1：

    • 目标两数之和为 -a = 1。
    • 检查去重：nums[1] == nums[0] (-1 == -4?) 不相等，所以继续。
    • 初始化指针：left = 2, right = 5。
    • 进入循环：
      • 和 = nums[2] + nums[5] = -1 + 2 = 1。等于目标值1！
      • 记录三元组 [-1, -1, 2]。
      • 去重操作：left 从2移动到3 (跳过重复的 -1)，right 从5移动到4 (2是唯一的)。
    • 新一轮循环：left = 3, right = 4。
      • 和 = nums[3] + nums[4] = 0 + 1 = 1。等于目标值1！
      • 记录三元组 [-1, 0, 1]。
      • 去重操作：left 移动到4，right 移动到3。此时 left(4) 不再小于 right(3)，循环结束。

  4. i = 2, a = nums[2] = -1：

    • 目标两数之和为 -a = 1。
    • 关键去重：检查 nums[2] == nums[1] (-1 == -1?) 相等！这意味着如果我们以这个 -1 作为 a，找到的所有三元组 ( -1, x, y) 一定和 i=1 时找到的 (-1, x, y) 重复。因此，我们直接跳过，i++。

  5. i = 3, a = nums[3] = 0：

    • 目标两数之和为 -a = 0。
    • 指针：left = 4, right = 5。
    • 循环：和 = 1 + 2 = 3 > 0，right 左移。
    • right = 4, 此时 left(4) 不再小于 right(4)，循环结束。

  6. i = 4, a = nums[4] = 1：

    • 目标两数之和为 -1。
    • 提前终止检查：a > 0 吗？1 > 0。由于数组是升序的，a 以及它后面的所有数都大于0，三数之和不可能为0。因此，整个算法可以终止。

  7. 最终结果：

    • 收集到的三元组为：[[-1, -1, 2], [-1, 0, 1]]。

算法复杂度分析

  • 时间复杂度：O(n²)。排序的时间复杂度为 O(n log n)。外层循环固定 i 是 O(n)，内层的双指针循环在最坏情况下是 O(n)，因此总的是 O(n²)。远优于 O(n³)。
  • 空间复杂度：O(log n) 到 O(n)，取决于排序算法的实现。我们只需要常数空间存储几个指针和结果列表（结果列表不计入空间复杂度，因为它是输出要求）。

总结

这道“三数之和”问题巧妙地将“三数”问题通过固定一个数转化为经典的“两数之和”问题。利用排序为数组带来有序性，进而可以运用双指针技术在线性时间内解决转化后的子问题。整个算法的核心难点和精髓在于利用排序后的特性，进行高效的去重（跳过重复的固定数和跳过找到解后指针指向的重复值），这也是面试中考察的重点。

三数之和 题目描述 给你一个包含 n 个整数的数组 nums ，请你判断 nums 中是否存在三个元素 a ， b ， c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。 注意 ： 答案中不可以包含重复的三元组。 输入的数组长度 n 满足： 3 <= n <= 3000 。 数组元素的范围： -10^5 <= nums[i] <= 10^5 。 示例 ： 输入： 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 ，但 [-1, 0, 1] 和 [-1, -1, 2] 的组合都满足条件，且没有重复。 解题过程详解 核心思路 最直接的方法是三重循环枚举所有可能的 (a, b, c) 组合，检查其和是否为0，并去重。但这样做时间复杂度是 O(n³) ，对于 n 最大为3000来说是不可接受的。我们需要一个更高效的策略。 核心优化思想 ：固定其中一个数，将三数之和问题转化为两数之和问题。 具体步骤如下： 排序数组 ：首先对数组进行排序（例如升序排序）。这是后续进行高效搜索和去重的基础。 枚举固定数 ：遍历排序后的数组，将当前遍历到的元素 nums[i] 作为我们想要固定的第一个数 a 。 转化为两数之和问题 ：问题就变成了：在 nums[i] 之后的子数组中，寻找两个数 b 和 c ，使得 b + c = -a （即 0 - nums[i] ）。 高效寻找两数之和 ：对于已排序的数组，寻找和为特定目标值的两个数，可以使用 双指针法 。初始化一个左指针 left 指向 i+1 ，右指针 right 指向数组末尾 n-1 。计算 nums[left] + nums[right] 的和，与目标值 -nums[i] 比较： 如果和 > 目标值 ，说明 nums[right] 太大了，将 right 左移一位。 如果和 < 目标值 ，说明 nums[left] 太小了，将 left 右移一位。 如果和 = 目标值 ，则找到一组解 (nums[i], nums[left], nums[right]) 。记录后，需要移动指针寻找其他可能的解，同时要跳过重复的元素以避免重复的三元组。 关键的去重 ： 对于固定的第一个数 a ( nums[i] )，如果它和前一个固定的数相同（即 nums[i] == nums[i-1] ），那么以它开头的所有三元组必定和以 nums[i-1] 开头的三元组重复。因此，我们可以跳过它，直接 continue 。 当找到一组解后，我们需要移动 left 和 right 指针。在移动时，如果下一个 left 指向的值与当前值相同，那么 (nums[i], nums[left+1], nums[right]) 这个三元组和刚找到的会是重复的。因此，我们需要一个 while 循环，将 left 一直移动到下一个不同的值。同理，对于 right 指针也需要一个向左移动的 while 循环来跳过重复值。 提前终止 ：由于数组已排序，如果固定的第一个数 nums[i] 已经大于0，那么它后面所有的数都大于0，三数之和不可能为0，可以直接结束整个循环。 详细步骤分解（以示例 nums = [-1, 0, 1, 2, -1, -4] 为例） 排序 ： 排序后的数组为： nums = [-4, -1, -1, 0, 1, 2] 开始遍历，固定第一个数 a （下标 i ） ： i = 0 , a = nums[0] = -4 。目标两数之和为 -a = 4 。 初始化双指针： left = i+1 = 1 , right = 5 。 进入 while (left < right) 循环： 计算 nums[left] + nums[right] = -1 + 2 = 1 。 1 < 4 ，和太小， left 右移。 left = 2 , 和 = -1 + 2 = 1 ，仍然小于4， left 右移。 left = 3 , 和 = 0 + 2 = 2 ，小于4， left 右移。 left = 4 , 和 = 1 + 2 = 3 ，小于4， left 右移。 left = 5 ，此时 left 不再小于 right ，循环结束。未找到和为4的组合。 i 移动到下一位。 i = 1 , a = nums[1] = -1 ： 目标两数之和为 -a = 1 。 检查去重： nums[1] == nums[0] (-1 == -4?) 不相等，所以继续。 初始化指针： left = 2 , right = 5 。 进入循环： 和 = nums[2] + nums[5] = -1 + 2 = 1 。 等于目标值1 ！ 记录三元组 [-1, -1, 2] 。 去重操作： left 从2移动到3 (跳过重复的 -1)， right 从5移动到4 (2是唯一的)。 新一轮循环： left = 3 , right = 4 。 和 = nums[3] + nums[4] = 0 + 1 = 1 。 等于目标值1 ！ 记录三元组 [-1, 0, 1] 。 去重操作： left 移动到4， right 移动到3。此时 left(4) 不再小于 right(3) ，循环结束。 i = 2 , a = nums[2] = -1 ： 目标两数之和为 -a = 1 。 关键去重 ：检查 nums[2] == nums[1] (-1 == -1?) 相等 ！这意味着如果我们以这个 -1 作为 a ，找到的所有三元组 ( -1, x, y) 一定和 i=1 时找到的 (-1, x, y) 重复。因此，我们直接跳过， i++ 。 i = 3 , a = nums[3] = 0 ： 目标两数之和为 -a = 0 。 指针： left = 4 , right = 5 。 循环：和 = 1 + 2 = 3 > 0， right 左移。 right = 4 , 此时 left(4) 不再小于 right(4) ，循环结束。 i = 4 , a = nums[4] = 1 ： 目标两数之和为 -1 。 提前终止检查 ： a > 0 吗？1 > 0。由于数组是升序的， a 以及它后面的所有数都大于0，三数之和不可能为0。因此，整个算法可以终止。 最终结果 ： 收集到的三元组为： [[-1, -1, 2], [-1, 0, 1]] 。 算法复杂度分析 时间复杂度 ： O(n²) 。排序的时间复杂度为 O(n log n) 。外层循环固定 i 是 O(n) ，内层的双指针循环在最坏情况下是 O(n) ，因此总的是 O(n²) 。远优于 O(n³) 。 空间复杂度 ： O(log n) 到 O(n) ，取决于排序算法的实现。我们只需要常数空间存储几个指针和结果列表（结果列表不计入空间复杂度，因为它是输出要求）。 总结 这道“三数之和”问题巧妙地将“三数”问题通过 固定一个数 转化为经典的“两数之和”问题。利用 排序 为数组带来有序性，进而可以运用 双指针 技术在线性时间内解决转化后的子问题。整个算法的核心难点和精髓在于利用排序后的特性，进行 高效的去重 （跳过重复的固定数和跳过找到解后指针指向的重复值），这也是面试中考察的重点。