- 正确答案：三数之和为0问题要求在给定整数数组中找出所有不重复的三元组（a, b, c），使得 a + b + c = 0。标准解法是先排序，再使用双指针技术遍历固定一个数，对剩余区间用左右指针收缩查找匹配对。关键在于去重逻辑：对固定值i、左指针l、右指针r均需跳过连续重复元素，避免结果重复。 - 解答思路： 1. 对数组升序排序（O(n log n)），为双指针提供单调性基础； 2. 外层循环固定第一个数nums[i]，i从0到n-3； 3. 若nums[i] > 0，由于已排序，后续三数之和必>0，直接break； 4. 跳过重复的nums[i]（i > 0 && nums[i] == nums[i-1]），避免同一基准导致重复解； 5. 设置左指针l = i+1，右指针r = n-1，在子区间[i+1, n-1]内查找nums[l] + nums[r] == -nums[i]； 6. 若和小于目标，l++；大于则r--；等于则加入结果，并同时跳过nums[l]和nums[r]的重复值（l < r && nums[l]==nums[l+1] → l++；同理r）； 7. 循环结束后返回所有三元组。 - 深度知识讲解：【底层原理】该算法本质是将O(n³)暴力枚举优化为O(n²)，核心依赖于排序后数组的有序性——使双指针具备方向性决策能力：当sum < target时，唯一增大和的方式是右移左指针（增大较小加数）；反之左移右指针（减小较大加数）。这是贪心策略在双指针中的体现。【去重机制深度剖析】去重不是简单“HashSet存结果再去重”，而是前置逻辑剪枝： - 固定值去重：若nums[i] == nums[i-1]，说明以nums[i-1]为基准时已穷举过所有含该值的合法三元组，当前轮次必然产生重复，故continue； - 左右指针去重：找到一组解后，若不跳过相邻重复值，下一次l++或r--仍可能命中相同数值，导致同一三元组不同排列（如[-1,0,1]与[-1,1,0]虽顺序不同但集合相同）被多次加入；注意必须在加入结果后立即执行去重，且需while(l < r)保证边界安全；【稳定性与边界处理】算法不依赖额外哈希表，空间复杂度O(1)（忽略输出存储）；但需注意整数溢出风险：虽然题目限定为int数组，但-nums[i]可能为INT_MIN（如nums[i] = INT_MIN），此时取负会溢出。稳健实现应使用long target = -(long)nums[i] 或改用相减判断：nums[l] + nums[r] == -nums[i] → 等价于 nums[i] + nums[l] + nums[r] == 0，直接计算三数和并比较0，避免符号翻转溢出；【对比其他方法】 × 哈希表法（固定i，对j>i用HashSet查target - nums[i] - nums[j]）：时间O(n²)，但去重困难（需对每个三元组排序后存Set），且空间O(n)； × 二分查找法（固定i,j，二分查-(nums[i]+nums[j])）：时间O(n² log n)，无天然去重优势； √ 双指针法是最优解：时间O(n²)，空间O(1)，且去重逻辑清晰可验证。 - 代码示例（C++风格，含溢出防护和完整去重）： ``` vector> threeSum(vector& nums) { vector> res; int n = nums.size(); if (n < 3) return res; sort(nums.begin(), nums.end()); for (int i = 0; i < n - 2; ++i) { // 优化1：若最小值已大于0，则后续不可能和为0 if (nums[i] > 0) break; // 去重1：跳过重复的基准值 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) { res.push_back({nums[i], nums[left], nums[right]}); // 去重2：跳过left侧重复 while (left < right && nums[left] == nums[left + 1]) left++; // 去重3：跳过right侧重复 while (left < right && nums[right] == nums[right - 1]) right--; left++; right--; } else if (sum < 0) { left++; } else { right--; } } } return res; } ``` - 扩展知识点： 1. 可推广至“四数之和”：外层两重循环固定两个数，内层双指针；时间O(n³)，去重需对前两个数分别去重； 2. “最接近的三数之和”：类似框架，维护全局最小abs(sum - target)及对应三元组； 3. 若要求返回索引而非值，排序会破坏原始索引，需预存{value, index} pair并自定义排序，或改用哈希表法； 4. 在并发场景下，该算法天然适合分段并行（不同i区间独立），但需注意结果合并去重； 5. 面试常追问：能否优化到O(n log n)？答案是否定的——三数之和存在Ω(n²)的计算复杂度下界（需至少检查O(n²)对组合），已被理论证明。

满帮 校招 数据开发 面经

全站热榜

创作者周榜

满帮校招数据开发面经