四数之和怎么从三数之和扩展？剪枝和去重应该怎么写？

简化版

四数之和通常先排序，再固定前两个数，把问题降成有序数组上的两数之和。

去重要发生在每一层：第一个数去重、第二个数去重、左右指针命中后也要跳过重复值。

如果当前最小和已经大于目标，或者当前最大和仍小于目标，可以提前剪枝。

详细版

四数之和的基本思路是“排序 + 两层枚举 + 双指针”。

先把数组升序排序。外层枚举 i，内层枚举 j，剩下的区间 [j + 1, n - 1] 用左右指针找 target - nums[i] - nums[j]。

当四数和等于目标时，记录答案，并同时移动 left 和 right，跳过重复元素。

当四数和小于目标时，说明需要更大的数，移动 left；当四数和大于目标时，移动 right。

复杂度是 O(n^3)，空间复杂度不算输出是 O(1)。排序后去重能保证结果中没有重复四元组。

完整版教学

一、为什么四数之和不是直接四层循环

暴力做法枚举 4 个下标，复杂度是 O(n^4)。当 n = 200 时，组合数量大约是 200^4 = 1,600,000,000 级别，面试里通常不可接受。四数之和的突破口是排序后保留有序性，把最后两层循环变成一次线性双指针扫描。这样外面两层是 O(n^2)，里面双指针是 O(n)，总复杂度降到 O(n^3)。

记忆钩子：K 数之和的常见降维方式是“固定若干个数，把最后 2 个数交给双指针”。

二、排序带来了什么能力

排序不是为了好看，而是为了让左右指针有明确移动方向。若当前和太小，移动左指针能让和变大；若当前和太大，移动右指针能让和变小。没有排序时，指针移动没有单调依据，不能保证不会漏解。

当前四数和	目标关系	移动方式	原因
`sum < target`	偏小	`left++`	需要更大的第三/第四个数
`sum > target`	偏大	`right--`	需要更小的第三/第四个数
`sum == target`	命中	两边都移动	当前组合已记录，需要找新组合

这个表就是双指针正确性的来源。

三、完整流程怎么拆

可以把算法拆成 3 层：

第 1 层：枚举 i，固定第一个数
第 2 层：枚举 j，固定第二个数
第 3 层：left/right 在剩余区间里找两数之和

代码骨架如下：

function fourSum(nums, target) {
  nums.sort((a, b) => a - b)
  const ans = []
  const n = nums.length
  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue
    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue
      let left = j + 1
      let right = n - 1
      while (left < right) {
        const sum = nums[i] + nums[j] + nums[left] + nums[right]
        if (sum === target) {
          ans.push([nums[i], nums[j], nums[left], nums[right]])
          left++
          right--
          while (left < right && nums[left] === nums[left - 1]) left++
          while (left < right && nums[right] === nums[right + 1]) right--
        } else if (sum < target) {
          left++
        } else {
          right--
        }
      }
    }
  }
  return ans
}

面试时不必一开始就背完代码，先讲清楚降维过程更重要。

四、去重为什么要分层处理

四数之和的重复来源有 3 个位置。第一层 i 如果和上一个值相同，固定它得到的组合会重复；第二层 j 同理；命中后左右指针也要跳过相同值，否则同一组数会被反复加入答案。注意去重比较的是值，不是下标，因为题目通常要求“不重复四元组”。

举例：nums = [1,1,1,2,2,3]，如果不跳过重复的 i = 1，会产生和 i = 0 一样的开头。命中 [1,1,2,3] 后，如果 left 停在另一个 2 上，也会再次得到同样四元组。

五、剪枝怎么做才安全

排序后可以用最小可能和、最大可能和剪枝。固定 i 后，如果 nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target，后面只会更大，可以直接 break。如果 nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target，当前 i 太小，可以 continue。

同理固定 j 后，也能用后面两个最小值、两个最大值做判断。剪枝要建立在排序基础上，并且不能把可能答案排除掉。

六、常见误区与追问

误区：四数之和直接套三数之和但只去重一层。 四元组重复可能来自 i、j、left/right 三个层面，少一层都会出重复答案。
误区：命中后只移动 left。 如果只移动一侧，另一侧重复值可能导致重复记录，也会错过下一组组合。
误区：剪枝条件没有排序依据。 未排序数组上比较最小和、最大和没有意义，剪枝可能误删答案。
追问：复杂度还能低于 O(n^3) 吗？ 通用四数之和列出全部结果时通常很难，因为结果规模本身可能很大；哈希能换思路，但去重和空间成本更复杂。
追问：为什么不用 Set 暴力去重？ Set 能兜底，但会掩盖去重逻辑，且字符串化四元组有额外开销；面试更看重排序后的结构化去重。

这些问题集中考察“排序带来的单调性”和“多层去重边界”。

七、加强记忆

记四数之和可以抓住“固定两个，双指针两个”。先排序，让和的变化可控；外层固定 i 和 j，每层都跳过重复值；内层用 left/right 根据和偏小或偏大移动。剪枝时只相信排序能证明的最小和和最大和。这样从三数之和扩到四数之和时，核心思想不变，只是多了一层固定和更多去重位置。

简化版

详细版