- 正确答案：三数之和问题要求在给定的整数数组中找出所有不重复的三元组，使得这三个数的和为零。解决该问题的经典方法是使用排序 + 双指针技术，时间复杂度为 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. 如果三数之和等于 0，将该三元组加入结果集，并跳过重复元素以避免重复解。 4. 如果和小于 0，说明左指针需要右移以增大总和；如果大于 0，则右指针左移以减小总和。 5. 外层循环中也要跳过重复的 nums[i] 值，确保每个三元组唯一。 - 深度知识讲解：考点一：排序与双指针优化暴力解法是三层嵌套循环，时间复杂度 O(n³)，无法通过大多数测试用例。通过排序后使用双指针技巧，可以将内层两个循环压缩为 O(n)，从而整体降至 O(n²)。考点二：去重机制由于题目要求“不可包含重复的三元组”，必须处理重复元素。关键在于： - 在外层 for 循环中，若 nums[i] == nums[i-1]（i > 0），则跳过当前 i，防止以相同数值作为第一个元素重复计算。 - 当找到一个有效三元组后，在移动 left 和 right 时，也要跳过与其值相同的连续元素。考点三：边界条件控制数组长度小于 3 时直接返回空列表。排序后若首个元素已大于 0，则不可能有三数之和为 0，可提前终止。考点四：数据结构选择使用 List> 存储结果，不需要额外哈希表去重，靠逻辑去重更高效且节省空间。若使用 HashSet 自动去重，会增加哈希计算开销，不推荐。考点五：算法稳定性与正确性排序改变了原始索引位置，但题目不要求返回下标，因此允许排序。这是典型的“牺牲索引信息换取效率提升”的策略。扩展知识点：类似问题包括“四数之和”、“最接近的三数之和”，均可采用类似框架扩展。例如四数之和可固定前两个数，再用双指针处理后两个数。 - 代码示例（Java 风格伪代码，适用于手撕）： ``` public List> threeSum(int[] nums) { List> result = new ArrayList<>(); if (nums.length < 3) return result; // 排序 Arrays.sort(nums); for (int i = 0; i < nums.length - 2; i++) { // 提前剪枝：最小值都大于0，无解 if (nums[i] > 0) break; // 去重：跳过相同的第一个数 if (i > 0 && nums[i] == nums[i - 1]) continue; int left = i + 1; int right = nums.length - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { result.add(Arrays.asList(nums[i], nums[left], nums[right])); // 去重：跳过相同的 left 和 right 值 while (left < right && nums[left] == nums[left + 1]) left++; while (left < right && nums[right] == nums[right - 1]) right--; // 移动指针 left++; right--; } else if (sum < 0) { left++; // 和太小，左指针右移 } else { right--; // 和太大，右指针左移 } } } return result; } ``` 注意事项（面试中加分点）： - 写完代码后应主动分析时间复杂度：排序 O(n log n)，外层循环 O(n)，内层双指针最多扫描 n 次，合计 O(n²)，主导项为 O(n²)。 - 强调去重逻辑的位置和必要性，特别是内外两层去重都要做。 - 可指出该算法不能用于要求返回索引的情况，因为排序破坏了原数组顺序。 - 若面试官问是否可用哈希表，可回答：虽然可以用哈希表记录补数，但在三重循环中仍难避免重复组合，且去重成本高，不如双指针清晰高效。总结：三数之和是高频考察题，重点在于掌握“排序+双指针+去重”三位一体的编码模式，理解每一步的设计动机，才能在压力下手撕无误。

美团搜索推荐算法一面

全站热榜

创作者周榜