三数之和算法：双指针技巧与面试优化策略

1. 三数之和问题解析三数之和3Sum是算法面试中最经典的问题之一也是LeetCode上被标记为中等难度的热门题目。这道题看似简单却蕴含着许多算法设计的精妙之处能够很好地考察面试者对双指针技巧、边界条件处理以及算法优化的理解。问题的核心要求是给定一个包含n个整数的数组nums找出所有满足条件的三元组[nums[i], nums[j], nums[k]]使得i ≠ j ≠ k且nums[i] nums[j] nums[k] 0。解集中不能包含重复的三元组。注意这道题之所以成为面试高频题是因为它完美地结合了基础算法思想和实际编码能力考察。据统计在头部科技公司的算法面试中这道题的出场率高达35%。2. 暴力解法与优化思路2.1 三重循环暴力解法最直观的解法是使用三重循环枚举所有可能的三元组组合def threeSum(nums): n len(nums) result [] 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 result: result.append(triplet) return result这种解法的时间复杂度是O(n³)在n较大时如n3000会变得极其缓慢。例如当n3000时需要执行约3000³27,000,000,000次操作这在面试中是完全不可接受的。2.2 排序双指针优化我们可以通过以下优化将时间复杂度降低到O(n²)首先对数组进行排序O(n log n)固定一个数nums[i]然后在剩余部分使用双指针寻找两数之和等于-nums[i]的组合通过跳过重复元素来避免重复解def threeSum(nums): nums.sort() n len(nums) result [] for i in range(n-2): if i 0 and nums[i] nums[i-1]: continue # 跳过重复元素 left, right i1, n-1 target -nums[i] while left right: current_sum nums[left] nums[right] if current_sum target: result.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 elif current_sum target: left 1 else: right - 1 return result3. 关键细节与边界条件3.1 去重处理的艺术去重是这道题最容易出错的地方之一。我们需要在三个层面上处理重复外层循环的固定元素去重当nums[i] nums[i-1]时跳过找到解后左指针的去重跳过所有与nums[left]相同的元素找到解后右指针的去重跳过所有与nums[right]相同的元素我在实际面试中遇到过候选人正确实现了双指针部分却因为去重处理不当而功亏一篑。记住去重检查应该在找到有效解之后进行而不是在移动指针时。3.2 提前终止条件我们可以添加一些提前终止的条件来优化性能如果nums[i] 0可以直接终止循环因为数组已排序后面的数都更大不可能三数之和为0如果nums[i] nums[i1] nums[i2] 0可以提前终止如果nums[i] nums[-2] nums[-1] 0可以跳过当前i继续下一个# 在for循环中添加这些优化 if nums[i] 0: break if nums[i] nums[i1] nums[i2] 0: break if nums[i] nums[-2] nums[-1] 0: continue4. 复杂度分析与变种问题4.1 时间复杂度分解排序O(n log n)外层循环O(n)内层双指针O(n)总体O(n log n) O(n) * O(n) O(n²)虽然理论复杂度是O(n²)但由于有提前终止的优化实际运行时间通常会比纯O(n²)更好。4.2 常见变种问题最接近的三数之和3Sum Closest找到和最接近目标值的三元组较小的三数之和3Sum Smaller统计和小于目标值的三元组数量四数之和4Sum扩展到四个数的组合三数之和的多种解法使用哈希表替代双指针以最接近的三数之和为例解法框架类似但需要维护一个最小差值def threeSumClosest(nums, target): nums.sort() n len(nums) closest float(inf) for i in range(n-2): left, right i1, n-1 while left right: current_sum nums[i] nums[left] nums[right] if abs(current_sum - target) abs(closest - target): closest current_sum if current_sum target: left 1 elif current_sum target: right - 1 else: return target return closest5. 面试实战技巧5.1 白板编码时的注意事项先明确问题要求确认是否可以修改原数组、是否需要考虑溢出等边界条件从暴力解法开始然后逐步优化展示思考过程特别注意去重逻辑的解释这是面试官常关注的细节主动讨论时间/空间复杂度并思考优化可能5.2 常见面试问题准备面试官可能会追问如果数组很大无法放入内存怎么办可以考虑外部排序分块处理的方案如何测试你的代码应包含全正数、全负数、有正有负、重复元素等多种情况哈希表解法为什么不如双指针哈希表需要额外空间且去重更复杂5.3 代码模板与记忆要点以下是可记忆的代码模板框架排序数组外层循环固定第一个数跳过重复提前终止判断内层双指针搜索找到解后跳过重复根据当前和调整指针返回结果记住这个框架可以快速应对面试中的类似问题。