1. 为什么三数之和是算法面试的必考题三数之和问题3Sum在LeetCode上被标记为中等难度但它的实际地位远超这个标签。作为算法面试中的经典问题它完美融合了多个核心考点基础算法能力检验需要熟练掌握排序、双指针等基础技巧边界条件处理考验对重复解、空输入等特殊情况的考虑时间复杂度优化从暴力解法的O(n³)优化到O(n²)的过程极具教学意义编码实现细节如何在保证正确性的前提下写出简洁优雅的代码我在面试候选人时发现90%的初级开发者能写出暴力解法但只有不到30%能完整实现优化方案。这道题就像一面镜子能清晰反映出程序员的算法思维水平。2. 问题描述与暴力解法分析2.1 问题正式定义给定包含n个整数的数组nums判断是否存在三元组[a, b, c]满足a b c 0不能包含重复的三元组示例 输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2], [-1,0,1]]2.2 暴力解法实现与缺陷最直观的解法是三层循环枚举所有可能组合def threeSum(nums): res [] n len(nums) for i in range(n): for j in range(i1, n): for k in range(j1, n): if nums[i] nums[j] nums[k] 0: triplet sorted([nums[i], nums[j], nums[k]]) if triplet not in res: res.append(triplet) return res这个解法存在三个明显问题时间复杂度O(n³)在n3000时计算量达到27亿次使用sorted和list判断去重效率极低没有利用输入数据的任何特性实测当n3000时暴力解法在普通笔记本上需要超过10分钟才能完成3. 优化思路排序双指针3.1 算法核心思想优化方案基于两个关键观察排序的价值有序数组可以避免重复解的自然产生双指针技巧固定一个数后问题退化为两数之和可以用双指针高效解决3.2 详细步骤拆解排序预处理O(nlogn)nums.sort()外层循环固定第一个数for i in range(len(nums)-2): if i 0 and nums[i] nums[i-1]: # 去重 continue left, right i1, len(nums)-1内层双指针搜索while left right: total nums[i] nums[left] nums[right] if total 0: left 1 elif total 0: right - 1 else: res.append([nums[i], nums[left], nums[right]]) # 跳过重复元素 while left right and nums[left] nums[left1]: left 1 while left right and nums[right] nums[right-1]: right - 1 left 1 right - 13.3 时间复杂度分析排序O(nlogn)外层循环O(n)内层双指针O(n)总体O(nlogn) O(n²) O(n²)相比暴力解法的O(n³)当n3000时计算量从27亿次降至约900万次提速300倍。4. 实现中的关键细节与避坑指南4.1 去重处理的三种场景外层循环去重if i 0 and nums[i] nums[i-1]: continue避免固定相同的数导致重复解如[-1,-1,0,1]中跳过第二个-1找到解后的左指针去重while left right and nums[left] nums[left1]: left 1确保下一个解的左元素不同找到解后的右指针去重while left right and nums[right] nums[right-1]: right - 1确保下一个解的右元素不同4.2 边界条件处理输入长度不足if len(nums) 3: return []全正数或全负数快速返回if nums[0] 0 or nums[-1] 0: return []最小和大于0或最大和小于0if nums[i] nums[i1] nums[i2] 0: break if nums[i] nums[-2] nums[-1] 0: continue4.3 常见错误模式去重时机错误错误在添加结果前去重可能漏解正确应在找到解后移动指针时去重指针移动逻辑反了if total 0: right - 1 # 错误应该增大和数忽略整数溢出 虽然Python不用担心但在C/Java中要考虑long total (long)nums[i] nums[left] nums[right];5. 算法变种与扩展思考5.1 最接近的三数之和LeetCode 16题要求找到和最接近target的三元组。解法类似只需维护一个最小差值变量根据当前和与target的关系移动指针实时更新最接近的解5.2 四数之和LeetCode 18题解法框架相同增加一层外层循环内层使用三数之和的解法时间复杂度升至O(n³)5.3 实际工程应用商品组合推荐电商中找出三件总价等于优惠门槛的商品实验设计选择三种试剂使浓度总和达标金融风控检测三笔关联交易金额之和异常6. 不同语言的实现对比6.1 Python实现特点def threeSum(nums): res [] nums.sort() for i in range(len(nums)-2): if i 0 and nums[i] nums[i-1]: continue left, right i1, len(nums)-1 while left right: s nums[i] nums[left] nums[right] if s 0: left 1 elif s 0: right - 1 else: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left1]: left 1 while left right and nums[right] nums[right-1]: right - 1 left 1 right - 1 return res优势代码简洁利用列表特性方便处理6.2 Java实现注意事项public ListListInteger threeSum(int[] nums) { Arrays.sort(nums); ListListInteger res new ArrayList(); for (int i 0; i nums.length-2; i) { if (i 0 nums[i] nums[i-1]) continue; int left i1, right nums.length-1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { left; } else if (sum 0) { right--; } else { res.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left right nums[left] nums[left1]) left; while (left right nums[right] nums[right-1]) right--; left; right--; } } } return res; }注意使用Arrays.asList创建不可变列表注意装箱问题6.3 C实现性能优化vectorvectorint threeSum(vectorint nums) { sort(nums.begin(), nums.end()); vectorvectorint res; for (int i 0; i nums.size()-2; i) { if (i 0 nums[i] nums[i-1]) continue; int left i1, right nums.size()-1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { left; } else if (sum 0) { right--; } else { res.push_back({nums[i], nums[left], nums[right]}); while (left right nums[left] nums[left1]) left; while (left right nums[right] nums[right-1]) right--; left; right--; } } } return res; }优势运行速度最快内存占用最小7. 刷题进阶训练建议7.1 同类题目推荐两数之和LeetCode 1三数之和最接近LeetCode 16四数之和LeetCode 18较小的三数之和LeetCode 259有效三角型的个数LeetCode 6117.2 训练方法三遍练习法第一遍独立思考并实现第二遍24小时后重新实现第三遍一周后尝试不同语言实现复杂度分析训练每次AC后手动计算时间复杂度对比讨论区最优解的复杂度测试用例设计最小输入空数组、不足三个数全正/全负数数组大量重复元素的情况极值测试3000个07.3 面试应答技巧先沟通再编码明确问题要求和边界条件先描述暴力解法再提出优化思路测试驱动开发先写出关键测试用例编码过程中逐步验证复杂度分析能够清晰解释每个步骤的时间复杂度了解算法瓶颈和改进空间我在准备算法面试时曾连续一周每天实现这个问题的不同变种。这种深度练习让我真正理解了双指针的精髓——不是记住解法而是培养对有序数据结构的敏感度。当你看到排序双指针的组合时要像看到老朋友一样自然。这才是算法练习的真正价值。
