- 正确答案：三数之和问题要求在给定整数数组中找出所有不重复的三元组 (a, b, c)，使得 a + b + c = 0。标准解法是先排序，再用双指针技术遍历，时间复杂度 O(n²)，空间复杂度 O(1)（不计输出空间）。关键在于去重逻辑：对第一个数（外层循环）去重时需跳过与前一个相同的值；对左右指针移动过程中的重复值也需跳过，避免重复三元组。 - 解答思路：第一步：对数组升序排序，为双指针提供单调性基础；第二步：固定第一个数 nums[i]（i 从 0 到 n−3），若 nums[i] > 0，则后续所有三数之和必大于 0，可直接 break（剪枝）；第三步：设置 left = i+1，right = n−1，在 [left, right] 区间内寻找 nums[i] + nums[left] + nums[right] == 0 的组合；第四步：若和小于 0，left++；大于 0，right--；等于 0 则记录结果，并执行去重：while(left < right && nums[left] == nums[left+1]) left++；while(left < right && nums[right] == nums[right−1]) right--；然后 left++, right-- 进入下一对；第五步：外层循环中，若 i > 0 且 nums[i] == nums[i−1]，则跳过，避免重复枚举相同首元素。 - 深度知识讲解：该题本质考察排序+双指针的协同设计能力，其底层依赖于「有序数组中两数之和」的经典模型。双指针有效性的数学基础是单调性：当数组升序时，nums[left] 随 left 增大而增大，nums[right] 随 right 减小而减小，因此 sum = nums[i] + nums[left] + nums[right] 关于 left 单调增、关于 right 单调减，可定向收缩搜索区间。去重机制是本题难点，必须区分「逻辑去重」与「物理去重」：不能用 HashSet 存三元组再去重（违背 O(1) 空间要求，且哈希开销大），而应利用排序后重复元素相邻的特性，在遍历过程中主动跳过。这体现了“预处理（排序）+ 贪心式跳过”的工程思维。时间复杂度分析：外层循环 O(n)，内层双指针最坏 O(n)，故总体 O(n²)；注意不是 O(n³)，因为 left 和 right 在单次外层循环中只会各自移动 O(n) 次（二者之和最多移动 n 次），这是双指针的关键性质——每个元素至多被访问常数次。对比暴力法 O(n³) 和哈希表优化的 O(n²)（如固定 i,j 查 -nums[i]-nums[j] 是否存在），双指针法无需额外哈希空间，且缓存局部性更好（连续内存访问），实际性能更优。边界细节：int 溢出风险虽在题目约束（-10⁵ ≤ nums[i] ≤ 10⁵）下极低，但严谨实现中，判断 sum 时建议用 long 或先比较符号再计算（例如：若 nums[i] > 0 且 nums[left] > 0 且 nums[right] > 0，则和必 > 0，可提前剪枝）；不过本题通常忽略此层。 - 代码示例（C++ 风格伪代码，含完整去重与剪枝）： ``` vector> threeSum(vector& nums) { vector> result; int n = nums.size(); if (n < 3) return result; sort(nums.begin(), nums.end()); for (int i = 0; i < n - 2; ++i) { if (nums[i] > 0) break; // 剪枝：最小数已>0，和不可能为0 if (i > 0 && nums[i] == nums[i-1]) continue; // 外层去重 int left = i + 1, right = n - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum < 0) { left++; } else if (sum > 0) { right--; } else { result.push_back({nums[i], nums[left], nums[right]}); // 内层去重：跳过所有相同 left 值 while (left < right && nums[left] == nums[left+1]) left++; // 内层去重：跳过所有相同 right 值 while (left < right && nums[right] == nums[right-1]) right--; left++; right--; } } } return result; } ``` - 扩展知识点： 1. 可推广至「四数之和」：外层两重循环固定前两个数，内层双指针找后两个数，时间复杂度 O(n³)，同样需严格去重； 2. 若要求返回索引而非值，且不允许重复使用同一索引，则需预存值→索引映射（但此时去重逻辑更复杂，因相同值可能对应不同索引）； 3. 若数组无序且禁止排序（如流式数据），可用哈希表：遍历 i，对每个 j > i，查 map 中是否存在 key = -nums[i]-nums[j]，并保证 j < k，但空间 O(n²)，且去重困难； 4. 工程实践提示：实际业务中，若数据量极大（如千万级），可考虑分块排序+归并，或用基数排序替代快排（当数值范围有限时），将排序优化至 O(n)； 5. 测试用例设计要点：需覆盖空数组、全零、两正一负和为零、重复数字密集（如 [-2,-2,-2,-1,-1,0,0,1,1,2,2]）、无解情况等，验证去重与剪枝正确性。

美团一面面经

全站热榜

创作者周榜