- 正确答案：三数之和问题要求在给定的整数数组中找出所有不重复的三元组，使得这三个数的和为0。解决该问题的经典方法是使用排序 + 双指针技术，时间复杂度为O(n²)，空间复杂度为O(1)（忽略结果存储）。示例输入：nums = [-1, 0, 1, 2, -1, -4] 输出：[[-1, -1, 2], [-1, 0, 1]] - 解答思路： 1. 首先对数组进行升序排序，便于后续去重和双指针操作。 2. 遍历数组，固定第一个数 nums[i]，然后在剩余部分使用双指针（left 和 right）寻找两个数，使得三者之和为0。 3. 对于每个 nums[i]，设置 left = i + 1，right = n - 1。 4. 计算三数之和 sum = nums[i] + nums[left] + nums[right]： - 如果 sum == 0，找到一组解，加入结果集，并移动 left 和 right 去重。 - 如果 sum < 0，说明左指针需要右移以增大和。 - 如果 sum > 0，说明右指针需要左移以减小和。 5. 外层循环中要跳过重复的 nums[i]，避免重复三元组。 6. 内部双指针移动时也要跳过重复值，确保结果唯一。 - 深度知识讲解：考点一：排序与双指针优化原始暴力解法是三层嵌套循环 O(n³)，但通过排序后可以利用有序性将内层两重循环优化为双指针扫描。这是“两数之和”思想的扩展。排序后，我们可以通过调整左右边界来逼近目标值，从而减少不必要的枚举。考点二：去重机制由于题目要求结果不能有重复三元组，必须处理重复元素： - 外层 i 去重：if (i > 0 && nums[i] == nums[i-1]) continue; - 内层 left 和 right 在找到解后需跳过相同值：while (left < right && nums[left] == nums[left+1]) left++; 同理 right。考点三：边界条件控制注意数组长度小于3时直接返回空列表；循环范围是 i < n - 2，因为至少要留出两个位置给 left 和 right。考点四：数据结构选择使用 List> 存储结果，外层 list 表示多个三元组，内层 list 表示一个三元组。Java 中可用 ArrayList 实现。考点五：算法稳定性与正确性排序破坏了原始索引关系，但本题只关心数值组合而非下标，因此合法。双指针法在有序数组上能保证不遗漏可行解，因为每次移动都是朝着目标（sum=0）方向推进。 - 代码示例（Java风格伪代码，适用于手撕）： ``` function threeSum(nums): if nums.length < 3: return empty list sort(nums) result = empty list for i from 0 to nums.length - 3: // 去重：跳过相同的第一个数 if i > 0 and nums[i] == nums[i-1]: continue left = i + 1 right = nums.length - 1 while left < right: sum = nums[i] + nums[left] + nums[right] if sum == 0: add [nums[i], nums[left], nums[right]] to result // 去重：跳过相同的 left 和 right while left < right and nums[left] == nums[left + 1]: left = left + 1 while left < right and nums[right] == nums[right - 1]: right = right - 1 // 移动指针 left = left + 1 right = right - 1 else if sum < 0: left = left + 1 // 和太小，左指针右移 else: right = right - 1 // 和太大，右指针左移 return result ``` - 扩展知识点： 1. 类似题目： - 四数之和：可基于三数之和嵌套一层循环，或继续用双指针。 - K数之和：可用递归+双指针通解，K>2时通常排序+回溯剪枝或迭代缩小问题规模。 2. 时间复杂度分析： - 排序耗时 O(n log n) - 外层循环 O(n)，内层双指针最多走 O(n) 距离 - 总体时间复杂度 O(n²) 3. 空间复杂度： - 排序所需栈空间 O(log n)（快速排序） - 结果存储最坏情况 O(n²) 个三元组（如全零数组），但题目一般不要求计入 - 辅助变量 O(1) 4. 特殊情况处理： - 全零数组：只有一个有效三元组 [0,0,0]，但可能多次匹配，必须去重。 - 数组中有大量重复元素：去重要严格，否则会输出多个相同三元组。 5. 进阶优化： - 提前终止：若 nums[i] > 0，则后面所有数都大于0，无法构成和为0，break。 - 剪枝：若当前最小三数之和仍大于0（如 nums[i] + nums[i+1] + nums[i+2] > 0），break；若最大三数之和仍小于0（如 nums[i] + nums[n-2] + nums[n-1] < 0），continue。 - 总结：三数之和是面试高频题，考察排序、双指针、去重逻辑、边界处理等综合能力。掌握其核心思想后可推广到更多变种问题。手撕时建议先写主框架，再补充去重和剪枝细节，保持代码清晰易读。

快手一二面凉经

全站热榜

创作者周榜