悠悠楠杉
网站页面
优化LeetCode三数之和问题：从超时到高效的两指针解法，leetcode 三数之和
11/29
![]()
在刷LeetCode的过程中，「三数之和」（第15题）是一道极具代表性的中等难度题目。它不仅考察对数组操作的理解，更考验对算法效率的敏感度。许多初学者的第一反应是暴力枚举三个数，结果往往是“超出时间限制”。本文将带你从超时的朴素解法出发，一步步推导出高效且优雅的两指针解法，深入剖析其中的思维转变与优化逻辑。
我们的问题是：给定一个整数数组 nums，找出所有满足 a + b + c = 0 的三元组 (a, b, c)，且结果中不能包含重复的三元组。例如输入 [-1,0,1,2,-1,-4]，期望输出 [[-1,-1,2],[-1,0,1]]。
最直观的想法是使用三层嵌套循环，枚举所有的 i, j, k 组合，判断三数之和是否为零。这样的时间复杂度是 $O(n^3)$，对于长度为 $10^3$ 的数组，计算量可达十亿级别，显然无法通过测试用例。此外，还需额外处理重复结果，比如先排序再用哈希表去重，但这依然无法拯救其糟糕的时间性能。
那么如何优化？关键在于减少不必要的枚举。如果我们能固定一个数，把问题转化为“在剩余数组中找两个数，使其和等于目标值”，这就变成了经典的“两数之和”问题。而一旦数组有序，这个问题就可以用双指针在线性时间内解决。
于是，整体思路浮现出来：先对数组排序，然后遍历每个元素作为第一个数，在其右侧的子数组中使用双指针寻找另外两个数。排序的时间复杂度是 $O(n \log n)$，外层循环 $O(n)$，内层双指针扫描 $O(n)$，总时间复杂度降为 $O(n^2)$，远优于暴力解法。
但真正的难点在于去重。即使算法变快了，如果不去除重复三元组，结果依然错误。考虑数组 [-1, -1, 0, 1, 1]，如果不加控制，可能会多次选到 -1, 0, 1 这个组合。因此，我们需要在两个层面做去重：一是外层循环中，若当前元素与前一个相同，则跳过，避免以相同数值开头产生重复；二是在双指针移动时，当找到一组解后，左右指针都要跳过所有相同的值，防止重复添加。
具体实现中，我们首先对数组排序。然后从索引 i = 0 开始遍历，直到 i < n-2（因为至少需要三个数）。对于每个 nums[i]，设定左指针 left = i + 1，右指针 right = n - 1。计算三数之和 sum = nums[i] + nums[left] + nums[right]。若 sum == 0，将三元组加入结果，并同时移动左右指针并去重；若 sum < 0，说明左边太小，left++；若 sum > 0，说明右边太大，right--。
这个过程中，排序不仅让双指针成为可能，还使得相同元素相邻，极大简化了去重逻辑。试想，如果没有排序，我们根本无法通过比较相邻元素来判断是否重复。
此外，还可以加入一些剪枝优化。例如，当 nums[i] > 0 时，由于数组已排序，后续所有数都大于零，三数之和不可能为零，可直接跳出循环。又如，当 nums[i] + nums[i+1] + nums[i+2] > 0，说明从当前位置开始的最小三数和都大于零，后续无需再查。
整个解法的核心思想是“降维”：通过固定一个变量，将三维搜索问题转化为二维，再借助有序性用双指针替代枚举。这种思维模式在很多数组类题目中都有体现，比如四数之和、最接近的三数之和等。
最终代码简洁清晰，时间效率显著提升，轻松通过所有测试用例。更重要的是，这一过程让我们体会到算法优化的本质——不是靠写更复杂的代码，而是靠更深刻的问题洞察。
