- 正确答案：四数之和问题要求在给定的整数数组中找出所有不重复的四个数的组合，使其和等于目标值。该问题可以通过排序加双指针的方法高效求解，时间复杂度为 O(n^3)，空间复杂度为 O(1)（不考虑结果存储空间）。 - 解答思路： 1. 首先对数组进行升序排序，便于后续去重和双指针操作。 2. 使用两层嵌套循环枚举前两个数 nums[i] 和 nums[j]（i < j），固定这两个数。 3. 对于剩下的两个数，使用双指针 left 和 right，分别从 j+1 和数组末尾向中间移动，寻找满足 nums[i] + nums[j] + nums[left] + nums[right] == target 的组合。 4. 在遍历过程中，跳过重复元素以避免重复解（去重）。 5. 如果四数之和等于目标值，将该四元组加入结果集，并移动双指针并跳过重复值；如果和小于目标值，left++；如果大于目标值，right--。 6. 循环结束后返回所有满足条件的四元组。 - 深度知识讲解：四数之和是“K数之和”问题的特例（K=4），属于经典的数组类算法问题，常用于考察对排序、双指针、去重逻辑和复杂度优化的理解。核心知识点包括： 1. **排序的作用**：排序后可以使用双指针技术将内层两个循环从 O(n^2) 优化到 O(n)，同时便于跳过重复元素。 2. **双指针技巧**：当数组有序时，left 从左向右，right 从右向左，根据当前和与目标值的关系决定移动方向，是一种典型的贪心策略。 3. **去重机制**： - 外层循环中，若 nums[i] == nums[i-1]，则跳过，避免重复固定相同的第一个数。 - 同理，在 j 循环中，若 nums[j] == nums[j-1] 且 j > i+1，则跳过。 - 在双指针部分，当找到一个解后，left 和 right 移动时也要跳过相同值。 4. **剪枝优化**： - 若当前最小可能和（当前四个数）都大于 target，可提前 break。 - 若当前最大可能和（如 nums[i] + nums[j] + nums[n-2] + nums[n-1]）小于 target，continue 尝试更大的 j。 - 这些优化可显著提升实际运行效率。该问题的底层数据结构是数组，依赖索引访问和顺序性。算法基于分治思想：外层枚举 + 内层双指针相当于将 4Sum 转化为多个 2Sum 子问题。而 2Sum 在有序数组中可用双指针在线性时间内解决。对比暴力解法（四重循环，O(n^4)），本方法通过排序和双指针将时间复杂度降至 O(n^3)，是典型的以空间换时间（虽未使用额外空间，但排序带来 O(n log n) 开销）并通过结构化搜索减少冗余计算的范例。 - 代码示例（Java 风格伪代码）： ``` List> fourSum(int[] nums, int target) { List> result = new ArrayList<>(); int n = nums.length; if (n < 4) return result; Arrays.sort(nums); for (int i = 0; i < n - 3; i++) { // 去重：跳过相同的 nums[i] if (i > 0 && nums[i] == nums[i-1]) continue; for (int j = i + 1; j < n - 2; j++) { // 去重：跳过相同的 nums[j] if (j > i + 1 && nums[j] == nums[j-1]) continue; int left = j + 1; int right = n - 1; while (left < right) { long sum = (long) nums[i] + nums[j] + nums[left] + nums[right]; // 防止整数溢出 if (sum == target) { result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); // 跳过重复值 while (left < right && nums[left] == nums[left + 1]) left++; while (left < right && nums[right] == nums[right - 1]) right--; left++; right--; } else if (sum < target) { left++; } else { right--; } } } } return result; } ``` - 扩展知识： 1. 类似问题包括三数之和（3Sum）、两数之和（2Sum），它们构成了“K数之和”系列。2Sum 最优解可用哈希表 O(n) 解决；3Sum 和 4Sum 通常用排序+双指针。 2. 若数组无序且不允许排序，4Sum 可用哈希表预处理两两之和，构建 HashMap>，然后枚举两对和等于 target，但需注意索引不重叠和去重问题，实现复杂且空间开销大。 3. 通用 KSum 可用递归方式实现：KSum → 枚举一个数 + (K-1)Sum，递归至 2Sum 终止。 4. 实际面试中，面试官可能要求处理整数溢出（如本例中用 long 接 sum），或返回下标而非数值，需注意题目细节。综上，四数之和是考察排序、双指针、去重和剪枝的综合题，掌握其思想可推广至更广泛的多维搜索去重问题。

26届秋招面经 ～ 小红书

全站热榜

创作者周榜

26届秋招面经～小红书