- 正确答案：三数之和问题要求在给定整数数组中找出所有不重复的三元组，使得它们的和为0。经典解法是先排序，再用双指针技术在O(n²)时间内求解。核心在于避免重复：跳过相同元素（对nums[i]、nums[left]、nums[right]均需去重），且保证三元组按升序排列（因已排序，自然满足）。 - 解答思路： 1. 对数组排序，使后续双指针收缩具有方向性，并便于去重； 2. 外层循环固定第一个数nums[i]，i从0到n-3； 3. 内层用left=i+1、right=n-1构成双指针，在子区间[i+1, n-1]中寻找nums[left] + nums[right] == -nums[i]的组合； 4. 若和小于目标（即nums[i]+nums[left]+nums[right] < 0），则left右移增大和；若大于目标，则right左移减小和；若等于，则记录结果，并同时跳过left右侧和right左侧的重复值； 5. 外层i遍历时，若nums[i] > 0，可提前终止（因已排序，后续三数之和必>0）；且若i>0且nums[i]==nums[i-1]，直接continue，避免重复三元组。 - 深度知识讲解：该题本质考察对排序+双指针范式的掌握，以及对“去重”这一高频边界问题的工程化处理能力。底层关键点包括： • 时间复杂度分析：排序O(n log n)，双层循环O(n²)，总体O(n²)，优于暴力O(n³)； • 空间复杂度：仅O(1)额外空间（不计结果存储），体现原地算法思想； • 去重原理：不是靠HashSet存tuple去重（会增加空间和哈希开销），而是利用有序性，在扫描过程中跳过相邻相同值——这是“排序预处理+顺序遍历去重”的典型模式，也是许多Two Sum变种（如四数之和、最接近的三数之和）的统一基础； • 双指针有效性证明：设当前i固定，target = -nums[i]，因数组升序，当nums[left] + nums[right] < target时，唯一增大和的方式是left++（right--只会让和更小）；反之亦然。该单调性由排序保障，是双指针正确性的数学基础； • 边界安全：left < right 的循环条件防止越界；i <= n-3确保剩余至少两个元素供双指针使用； • 稳定性与确定性：算法输出三元组按nums[i]升序排列，每个三元组内部也升序（因i 0: break # 外层去重：跳过与前一个相同的nums[i] if i > 0 and nums[i] == nums[i - 1]: continue left, right = i + 1, n - 1 while left < right: s = nums[i] + nums[left] + nums[right] if s < 0: left += 1 elif s > 0: right -= 1 else: result.append([nums[i], nums[left], nums[right]]) # 内层去重：跳过left右侧连续相同值 while left < right and nums[left] == nums[left + 1]: left += 1 # 内层去重：跳过right左侧连续相同值 while left < right and nums[right] == nums[right - 1]: right -= 1 # 移动双指针进入下一组搜索 left += 1 right -= 1 return result - 扩展知识： • 可扩展至kSum问题：采用递归+双指针（k=2时直接双指针，k>2时先枚举首元素，降维为(k-1)Sum）； • 若要求返回下标而非数值，需在排序前用enumerate保存原始索引，再按值排序并维护索引映射； • 若数组含大量重复元素，可进一步做频次压缩（如Counter预处理），但会破坏下标关系，适用于仅需数值解的场景； • 工程实践注意：输入校验（空数组、None）、整数溢出（本题Python无需，但C++需用long long防中间和溢出）； • 对比HashMap解法：暴力两层循环+HashMap查补数，时间O(n²)，空间O(n)，且去重更复杂（需对三元组排序后set去重），不如双指针优雅高效。

腾讯大模型实习一面-日常实习

全站热榜

创作者周榜