LeetCode 15：三数之和 | 双指针法详解与进阶应用

LeetCode 15：三数之和 | 双指针法详解与进阶应用

引言

三数之和（3Sum）是 LeetCode 中一道经典的高频面试题，编号为 15，属于 Medium 难度范畴。这道题的核心要求是在一个整数数组中找出所有不重复的三元组，使得这三个数之和为零。由于其看似简单但实现细节丰富的特点，三数之和成为了考察算法思维和代码实现能力的重要题目。

三数之和的暴力解法时间复杂度为 O(n³)，对于大规模数据显然无法接受。更优的解决方案采用双指针技巧，将时间复杂度降低到 O(n²)，同时通过巧妙的去重机制避免重复三元组的产生。本文将深入剖析双指针法解决三数之和的原理、实现细节以及各种边界情况的处理，帮助读者彻底掌握这一经典问题的解题思路。

问题分析

题目描述

给定一个整数数组 nums，判断是否存在元素 a、b、c 使得 nums[i] + nums[j] + nums[k] = 0（i ≠ j、i ≠ k 且 j ≠ k），并返回所有满足条件的不重复三元组。例如对于输入 [-1, 0, 1, 2, -1, -4]，满足条件的三元组有 [[-1, -1, 2], [-1, 0, 1]]。

问题特点

三数之和问题具有以下几个显著特点，使其成为算法学习中的经典案例。首先，由于需要返回所有满足条件的三元组，而不是仅仅判断是否存在，因此需要穷举所有可能的组合。其次，要求返回的三元组不能重复，这意味着需要对结果进行去重处理。最后，为了在 O(n²) 时间复杂度内解决此问题，必须采用高效的搜索策略，双指针法正是为此量身定做的技巧。

从更宏观的角度看，三数之和实际上是更广泛的 K 数之和问题的一个特例。当 K 大于 2 时，可以通过递归的方式将 K 数之和问题转化为若干个 (K-1) 数之和问题，但这种递归方法的时间复杂度会随着 K 的增大而指数增长。对于三数之和这一特殊情形，双指针法提供了更为优雅和高效的解决方案。

暴力解法分析

考虑最直接的暴力解法，我们可以使用三层嵌套循环遍历所有可能的三元组，检查其和是否为零。这种方法的时间复杂度为 O(n³)，空间复杂度为 O(1)。假设 n 为 1000，那么需要执行约 10 亿次运算，这对于现代计算机来说仍然是一个相当耗时的操作。更重要的是，暴力解法会产生大量重复的三元组，后续去重过程同样需要额外的时间和空间开销。

双指针法原理

排序预处理

双指针法解决三数之和的第一步是对数组进行排序。排序的目的有两个：一是通过将相等的元素聚集在一起，方便后续的去重操作；二是为双指针的移动提供方向性指导。排序后，数组呈现非递减的顺序，这意味着当指针指向某个元素时，我们可以根据该元素与目标值的关系来决定指针的移动方向。

排序操作的时间复杂度为 O(n log n)，这是双指针法总时间复杂度 O(n²) 中不可忽视的一部分。虽然排序增加了时间成本，但它为整个算法提供了重要的有序性保证，使得后续的搜索过程可以更加高效地进行。需要注意的是，排序会改变原有数组元素的相对位置，但由于我们只需要返回满足条件的三元组，而不需要知道这些三元组中元素的原始索引，因此这种改变是无害的。

固定一个数

在排序后的数组中，我们首先固定一个元素作为三元组中的第一个数。假设固定的是 nums[i]，那么问题就转化为在剩余的 nums[i+1] 到 nums[n-1] 范围内找到两个数，使它们的和等于 -nums[i]。这一步将原问题从三数之和转化为两数之和问题，而两数之和正是双指针法最经典的应用场景。

对于 nums[i] 的选择，我们需要特别注意去重。当 nums[i] 与前一个元素 nums[i-1] 相同时，如果继续以 nums[i] 为第一个数进行搜索，会产生与之前搜索重复的三元组。因此，当我们遇到连续相同的元素时，应该直接跳过，将 i 移动到下一个不同元素的位置。这种去重策略是双指针法高效性的重要保障。

两侧指针搜索

在确定了固定的第一个数 nums[i] 后，我们在 [i+1, n-1] 区间内设置两个指针：left 指向区间的左端点 i+1，right 指向区间的右端点 n-1。此时，我们的目标是找到 nums[left] + nums[right] = -nums[i] 的情况。如果三数之和大于零，说明需要减小总和，由于数组已排序，减小 right 指针可以减小 nums[right] 的值；如果三数之和小于零，说明需要增大总和，增大 left 指针可以增大 nums[left] 的值。

这一搜索过程持续进行，直到 left 和 right 指针相遇，此时我们已经检查了所有可能的二元组合。每次找到满足条件的三元组后，需要将 left 和 right 指针都向中间移动，并跳过所有与当前元素相同的值，以避免产生重复的三元组。这种移动策略确保了每个不同的三元组只会被发现一次。

完整代码实现

from typing import List class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: n = len(nums) if n < 3: return [] nums.sort() result = [] for i in range(n - 2): if nums[i] > 0: break if i > 0 and nums[i] == nums[i - 1]: continue left, right = i + 1, n - 1 target = -nums[i] while left < right: total = nums[left] + nums[right] if total == target: result.append([nums[i], nums[left], nums[right]]) while left < right and nums[left] == nums[left + 1]: left += 1 while left < right and nums[right] == nums[right - 1]: right -= 1 left += 1 right -= 1 elif total < target: left += 1 else: right -= 1 return result

上述实现中包含了几个关键的去重技巧。首先，在外层循环中跳过与前一个元素相同的 nums[i]，避免以相同的数字作为三元组的第一个元素。其次，在找到一个满足条件的三元组后，通过 while 循环跳过所有与 nums[left] 和 nums[right] 相同的元素，避免产生重复的三元组。这些去重操作确保了最终返回的结果集中不包含任何重复的三元组。

算法复杂度分析

时间复杂度

双指针法解决三数之和问题的时间复杂度为 O(n²)。这是因为外层循环最多遍历 n-2 次，而每次内层的双指针搜索过程在最坏情况下也会移动 O(n) 次。具体来说，外层循环的时间复杂度为 O(n)，内层双指针搜索的时间复杂度同样为 O(n)，两者相乘得到总时间复杂度 O(n²)。排序操作的时间复杂度 O(n log n) 在大 O 表示法中被更高级的 O(n²) 吸收，因此最终的时间复杂度仍为 O(n²)。

空间复杂度

算法的空间复杂度为 O(1)（不包括输出结果所占用的空间）。这是因为双指针法只需要使用常数个额外变量来存储指针位置、中间计算结果等，而不需要使用额外的数据结构来存储数组元素。返回的结果列表虽然占用了空间，但在计算空间复杂度时通常不计入输出参数所占用的空间。

边界情况处理

空数组和短数组

当输入数组的长度小于 3 时，无论如何都无法组成三元组，因此直接返回空列表。这是代码中最基本但也最容易忽略的边界检查。类似地，当数组中所有元素都大于零时，由于三个正数之和永远不可能为零，可以提前终止外层循环，这种优化在实际应用中可以显著减少不必要的计算。

包含重复元素的数组

去重是三数之和问题的核心难点之一。考虑输入 [-1, -1, -1, 2, 2, 2]，如果不去重，可能会产生多个相同的三元组 [-1, -1, 2]。去重策略的核心是：当我们在遍历过程中遇到与前一个元素相同的值时，直接跳过。这种策略基于一个重要的观察：如果以相同的值作为三元组的第一个（或第二个、第三个）元素，那么之前已经搜索过所有以该值开头的情况，再次搜索只会产生重复结果。

包含零的特殊情况

零在这个问题中具有特殊意义，因为 -nums[i] 本身可能为零。考虑输入 [-1, 0, 1, 2, -1, -4]，其中存在 nums[j] = 0 的情况。当 nums[i] + nums[j] + nums[right] = 0 时，意味着找到了一个包含零的三元组。由于零既不是正数也不是负数，它不会影响排序后数组的单调性，因此双指针的移动策略在包含零的情况下仍然有效。代码中对 nums[i] > 0 的提前终止条件需要特别注意，因为当 nums[i] = 0 时，即使后面的元素之和也为负，三数之和仍可能为零。

变种问题

四数之和（LeetCode 18）

四数之和是三数之和的直接扩展，要求在数组中找到四个数之和等于目标值。最直观的解法是固定两个数，然后使用双指针在剩余范围内寻找两个数，使四数之和等于目标值。这种方法的时间复杂度为 O(n³)，空间复杂度为 O(1)。另一种思路是使用哈希表将四数之和转化为两数之和问题，但空间复杂度会增加。对于四数之和，去重逻辑会更加复杂，需要同时对四个位置进行去重处理。

最接近的三数之和（LeetCode 16）

最接近的三数之和问题要求找到三个数，使它们的和最接近目标值。与原问题不同，这里不需要精确等于目标值，而是要找最接近的组合。解决这个问题可以在三数之和的基础上稍作修改：在遍历过程中，计算当前三数之和与目标值的差的绝对值，如果这个值比之前记录的最小差值更小，则更新结果。由于不需要精确相等，双指针的移动策略保持不变，但不需要进行去重操作。

统计三数之和为特定值的情况数

如果问题不是返回具体的三元组，而是统计三数之和等于目标值的情况数，那么可以去重优化，专注于计数。这种变种问题在某些实际应用场景中更常见，例如在统计分析中计算某种组合的总数。解决思路与标准三数之和类似，但在找到满足条件的三元组后，不是添加到结果集中，而是增加计数器的值。

实际应用场景

三数之和问题看似是一个纯学术性的算法问题，但它在许多实际应用场景中都有重要的应用价值。在数据分析领域，三数之和可以用于查找满足特定条件的组合，例如在金融数据分析中寻找收益为零的投资组合。在游戏开发中，三数之和的变种可以用于计算游戏中的得分组合或技能搭配。在图像处理和计算机视觉中，三数之和的思想也被用于特征匹配和三维重建等场景。

此外，双指针作为一种通用的问题解决技巧，其应用范围远不止三数之和问题。在处理有序数组的两数之和、两数之积、滑动窗口等问题时，双指针法都展现出了极高的效率。因此，深入理解三数之和问题的解决思路，对于提升整体算法能力具有重要意义。

总结

三数之和问题是一道经典的算法面试题，它巧妙地将双指针技巧与去重策略结合在一起，以 O(n²) 的时间复杂度解决了看似简单却细节丰富的问题。通过对这道题的学习，我们不仅掌握了双指针法的核心原理，还深入理解了处理重复元素的技巧。在实际面试中，三数之和及其变种问题经常出现，能够清晰准确地实现这道题的候选人往往能给面试官留下良好的印象。

通过本文的详细讲解，希望读者能够彻底掌握三数之和问题的解决方法，并将其中的算法思想融会贯通，应用于更多类似问题的解决中。双指针法作为一种强大的算法技巧，值得我们在实践中不断加深理解和应用。