- 正确答案：三数之和问题要求在给定整数数组中找出所有不重复的三元组 (a, b, c)，使得 a + b + c = 0。标准解法是先排序，再使用「固定一个数 + 双指针收缩」策略，时间复杂度 O(n²)，空间复杂度 O(1)（不计输出空间）。关键在于去重逻辑：对固定下标 i 去重需检查 nums[i] == nums[i-1]（且 i > 0）；对左右指针去重需在找到合法三元组后，跳过所有相同值的相邻元素。 - 解答思路：第一步：对数组升序排序，为双指针提供单调性基础，并便于统一去重。第二步：外层循环固定第一个数 nums[i]，i 从 0 到 n-3；若 nums[i] > 0，则后续所有三数之和必 > 0，可直接 break（剪枝）。第三步：设置 left = i+1，right = n-1，在 [left, right] 区间内寻找 nums[left] + nums[right] == -nums[i] 的组合。第四步：若和小于目标（即 -nums[i]），left++；若大于，right--；若等于，记录三元组，并执行去重：while(left < right && nums[left] == nums[left+1]) left++；while(left < right && nums[right] == nums[right-1]) right--；然后 left++, right-- 继续搜索。第五步：外层 i 去重：若 i > 0 且 nums[i] == nums[i-1]，跳过本次循环，避免重复三元组。 - 深度知识讲解：本题本质是「二维搜索空间上的线性扫描优化」，其底层依赖三个核心机制：（1）排序的数学意义：将无序集合转化为有序序列，使“两数之和”子问题可通过双指针 O(n) 解决（而非哈希表 O(n) 空间或暴力 O(n²) 时间），这是分治与贪心思想的结合。（2）双指针正确性证明：设已排序数组 A，目标 T = -nums[i]。当 A[l] + A[r] < T 时，A[l] 是当前左边界最小值，若固定 r，任何 l' < l 都会使和更小，故只能增大 l；同理 A[l] + A[r] > T 时只能减小 r。该性质源于数组单调性，是双指针可收敛的充要条件。（3）去重机制的底层实现原理：三重循环去重需保证每个等价类（由数值而非下标定义）仅被枚举一次。i 去重确保相同首元素只处理首次出现；left/right 去重确保同一 (i, target) 下，相同值的组合只取最外层一对（因内部重复值必然导致重复三元组）。注意：不能用 set 存储结果再去重，会退化为 O(n²) 空间且无法满足题目「不重复」的语义要求（set 无法保证插入顺序，且哈希开销大）。（4）边界安全设计：所有指针移动前必须校验 left < right，防止越界；i 循环上限为 n-3，因需预留至少两个元素给 left 和 right。（5）剪枝优化深度：当 nums[i] > 0 时，因数组已排序，nums[i] ≤ nums[i+1] ≤ nums[i+2]，故三数之和必 > 0，提前终止。同理，若 nums[i] + nums[i+1] + nums[i+2] > 0，说明最小可能和已超目标，可 break；若 nums[i] + nums[n-2] + nums[n-1] < 0，说明最大可能和仍不足，continue。这些属于「早停剪枝」，在实际数据中显著提升性能。 - 伪代码： ``` function threeSum(nums): if length(nums) < 3: return empty list sort(nums) result = empty list n = length(nums) for i from 0 to n-3: if nums[i] > 0: break if i > 0 and nums[i] == nums[i-1]: continue target = -nums[i] left = i + 1 right = n - 1 while left < right: sum = nums[left] + nums[right] if sum == target: append [nums[i], nums[left], nums[right]] to result // 去重 left while left < right and nums[left] == nums[left+1]: left = left + 1 // 去重 right while left < right and nums[right] == nums[right-1]: right = right - 1 left = left + 1 right = right - 1 else if sum < target: left = left + 1 else: right = right - 1 return result ``` - 扩展知识点：（1）对比「两数之和 II」（有序数组）：双指针是自然解法；而「两数之和 I」（无序）需哈希表，体现输入结构对算法选择的决定性影响。（2）推广至「四数之和」：可固定前两个数，内层双指针，时间复杂度 O(n³)；更优解法是「双指针嵌套」或「分治哈希」（如 meet-in-the-middle：拆成两两之和存哈希表，再查互补），体现高维组合问题的降维策略。（3）浮点数场景陷阱：若输入含浮点数，需考虑精度误差，此时应使用 epsilon 比较（如 abs(a+b+c) < 1e-9），而非直接判等。（4）内存局部性优化：排序后访问模式具有空间局部性（连续内存读取），CPU 缓存命中率高，实际运行快于哈希方案，体现算法与硬件协同设计思想。（5）函数式语言实现差异：在 Haskell 中可用 list comprehension + nub 去重，但时间复杂度退化为 O(n³ log n)，说明纯函数式表达需谨慎评估渐进复杂度。

26校招小红书NLP算法一面

全站热榜

创作者周榜