LeetCode 454 - 四数相加 II

摘要

LeetCode 454 是一道非常典型的“用空间换时间”的题。

如果你第一次看这道题，很容易写出一个四重循环，然后立刻发现：
完了，直接超时。

但这题真正考的不是暴力，而是你能不能意识到一件事：

四个数的和为 0，其实可以拆成两部分的和互相抵消。

一旦你从A + B + C + D = 0转成
(A + B) = -(C + D)
这道题的复杂度立刻从“不可做”变成了“非常稳”。

描述

题目给了你四个长度相同的整数数组：

• nums1
• nums2
• nums3
• nums4

要求你统计有多少个四元组(i, j, k, l)，满足：

nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

约束信息很关键

• 每个数组长度n <= 200
• 数值范围是[-2^28, 2^28]

这意味着什么？

• 四重循环是O(n^4)，最大是200^4，根本跑不完
• 必须降到O(n^2)级别

题解答案（核心思路）

关键拆分思路

把四个数组拆成两组：

• 第一组：nums1+nums2
• 第二组：nums3+nums4

目标条件：

a + b + c + d = 0

等价于：

(a + b) = -(c + d)

整体策略

1. 枚举nums1和nums2的所有和，记录每个和出现的次数
2. 枚举nums3和nums4的所有和
3. 对于每个(c + d)，查表看有没有-(c + d)
4. 累加出现次数

这一步的本质是：
把四数问题，降维成两个“两数之和”的问题。

题解答案（Swift 可运行 Demo）

classSolution{funcfourSumCount(_nums1:[Int],_nums2:[Int],_nums3:[Int],_nums4:[Int])->Int{varsumMap:[Int:Int]=[:]// 1. 统计 nums1 + nums2 的所有可能和forainnums1{forbinnums2{letsum=a+b sumMap[sum,default:0]+=1}}varresult=0// 2. 枚举 nums3 + nums4，寻找补数forcinnums3{fordinnums4{lettarget=-(c+d)ifletcount=sumMap[target]{result+=count}}}returnresult}}

题解代码分析

1. 为什么要用字典？

varsumMap:[Int:Int]=[:]

这里的字 considered 是：

• key：nums1[i] + nums2[j]
• value：这个和出现的次数

因为：

• 同一个和可能来自不同下标组合
• 每一种组合都要算进答案

2. 第一阶段：构建和的“频率表”

forainnums1{forbinnums2{letsum=a+b sumMap[sum,default:0]+=1}}

这一段做的事情很单纯：

• 枚举所有(i, j)
• 把a + b当成一个“中间结果”缓存起来

这一步的复杂度是：

O(n²)

3. 第二阶段：查补数并累加

lettarget=-(c+d)ifletcount=sumMap[target]{result+=count}

这里非常关键的一点是：

• 不是+1
• 而是+count

原因是：

• 可能有多个(a, b)对应同一个sum
• 每一种都能和当前(c, d)组成一个合法四元组

4. 为什么这样不会漏算或重复算？

因为：

• (a, b)只在第一阶段统计
• (c, d)只在第二阶段枚举
• 每个合法组合刚好被计算一次

示例测试及结果

示例 1

letsolution=Solution()letnums1=[1,2]letnums2=[-2,-1]letnums3=[-1,2]letnums4=[0,2]print(solution.fourSumCount(nums1,nums2,nums3,nums4))

输出：

2

示例 2

print(solution.fourSumCount([0],[0],[0],[0]))

输出：

1

自定义测试

print(solution.fourSumCount([1,-1],[-1,1],[0],[0]))

逻辑上：

(1 + -1) + (0 + 0) = 0 (-1 + 1) + (0 + 0) = 0

输出：

2

实际场景结合

这道题的思想在真实业务里非常常见。

1. 多条件组合统计

比如：

• 用户行为 A
• 用户行为 B
• 用户行为 C
• 用户行为 D

你想统计：
满足某个组合约束的用户数量

直接全量组合几乎一定炸。

2. 典型的“中间结果缓存”

• 把复杂问题拆成两半
• 把一半的结果预先算好并缓存
• 用另一半去查表

这是很多高性能系统的基本套路。

3. 面试中的信号题

这道题非常适合用来区分：

• 只会写暴力的人
• 能主动做复杂度分析、拆问题的人

时间复杂度

• 构建哈希表：O(n²)
• 查找补数：O(n²)

总时间复杂度：

O(n²)

空间复杂度

• 哈希表最多存n²个键值对

空间复杂度：

O(n²)

总结

LeetCode 454 的关键不在代码有多复杂，而在于你是否能意识到：

• 四数问题 ≠ 四重循环
• 拆分 + 哈希表是最稳的解法

如果你在刷题或写博客时，能把这道题讲清楚，基本就已经说明：

你不只是“会写题解”，而是真的理解了算法设计背后的思维方式。