1. 问题背景与核心思路
四数相加II是算法中一个经典的哈希表应用场景。给定四个整数数组nums1、nums2、nums3和nums4，要求统计有多少个元组(i,j,k,l)满足nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0。这个问题看似简单，但如果采用暴力解法，时间复杂度会达到O(n^4)，这在数据量较大时是完全不可接受的。
提示：当遇到需要统计满足特定条件的组合数量时，哈希表往往是优化时间复杂度的利器。
2. 哈希表解法详解
2.1 分组优化思路
我们可以将四个数组分成两组：
- 第一组：nums1和nums2
- 第二组：nums3和nums4
这样做的目的是将O(n^4)的时间复杂度降低到O(n^2)。具体步骤如下：
- 首先计算nums1和nums2中所有元素两两相加的和，并将这些和及其出现次数存入哈希表
- 然后计算nums3和nums4中所有元素两两相加的和的相反数
- 最后统计这些相反数在哈希表中出现的次数总和
2.2 具体实现步骤
def fourSumCount(nums1, nums2, nums3, nums4): from collections import defaultdict hashmap = defaultdict(int) # 计算nums1和nums2的两两和 for n1 in nums1: for n2 in nums2: hashmap[n1 + n2] += 1 count = 0 # 计算nums3和nums4的两两和的相反数 for n3 in nums3: for n4 in nums4: target = -(n3 + n4) if target in hashmap: count += hashmap[target] return count2.3 时间复杂度分析
- 构建哈希表阶段：O(n^2)
- 查询阶段：O(n^2)
- 总体时间复杂度：O(n^2)
- 空间复杂度：O(n^2)（哈希表存储所有可能的和）
3. 优化技巧与注意事项
3.1 哈希表选择
在Python中，我们通常使用defaultdict或Counter来构建哈希表。defaultdict在这里更合适，因为我们只需要简单的计数功能。
3.2 边界条件处理
- 空数组情况：如果任一数组为空，直接返回0
- 大数相加：注意整数溢出的问题（在Python中不需要特别处理，但在其他语言如C++中需要注意）
3.3 性能优化
- 可以优先处理较短的数组对，减少哈希表的大小
- 在实际编码中，可以将两个循环合并，减少代码行数
4. 扩展思考
4.1 类似问题
这种分组+哈希表的思路可以推广到其他类似问题：
- 三数之和
- 四数之和
- K数之和（当K较大时）
4.2 其他解法对比
虽然哈希表解法在这里最优，但也可以考虑：
- 排序+双指针法（时间复杂度相同，但实现更复杂）
- 暴力解法（仅适用于极小数据量）
5. 实际应用场景
这种算法在实际中有多种应用：
- 统计满足特定条件的组合
- 数据分析中的多维度匹配
- 密码学中的碰撞检测
6. 常见问题解答
6.1 为什么选择两两分组？
将四个数组分成两组是最优的分组方式，因为：
- 两组对称，实现简单
- 时间复杂度从O(n^4)降到O(n^2)
- 空间复杂度也在可接受范围内
6.2 如果数组长度不同怎么办？
算法对数组长度没有限制，不同长度仍然适用。哈希表的大小由前两个数组决定，查询阶段由后两个数组决定。
6.3 如何处理重复元素？
哈希表自动处理了重复元素的问题，因为我们是统计和的出现次数，而不是具体的元素组合。
7. 代码实现细节
7.1 Python实现优化
def fourSumCount(nums1, nums2, nums3, nums4): from collections import Counter AB = Counter(a+b for a in nums1 for b in nums2) return sum(AB[-c-d] for c in nums3 for d in nums4)这个实现更加简洁，利用了Python的生成器表达式和Counter的特性。
7.2 C++实现示例
#include <unordered_map> #include <vector> int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, int> hashmap; for (int a : nums1) for (int b : nums2) hashmap[a + b]++; int count = 0; for (int c : nums3) for (int d : nums4) if (hashmap.count(-(c + d))) count += hashmap[-(c + d)]; return count; }8. 测试用例设计
好的测试用例应该包含：
- 常规情况
- 边界情况（空数组）
- 大量重复元素
- 正负数混合
- 极值情况
示例测试用例：
assert fourSumCount([1,2], [-2,-1], [-1,2], [0,2]) == 2 assert fourSumCount([0], [0], [0], [0]) == 1 assert fourSumCount([], [], [], []) == 0 assert fourSumCount([1]*100, [-1]*100, [1]*100, [-1]*100) == 1000000009. 算法可视化理解
为了更好理解这个算法，可以想象：
- 首先将前两个数组的所有可能和计算出来，存入哈希表（类似建立了一个"和数据库"）
- 然后计算后两个数组的所有可能和的相反数，去"和数据库"中查询匹配
- 每匹配一次就增加对应的计数
这种"预处理+查询"的模式在很多算法中都有应用。
10. 进阶思考
如果问题变为找出所有满足条件的四元组而不仅仅是计数，该如何修改算法？
这种情况下，哈希表中需要存储的不是和的计数，而是和对应的索引对列表。这样在查询阶段，对于每个匹配的和，我们可以得到所有可能的索引组合。不过这会显著增加空间复杂度。
