哈希算法题目：四数相加 II 题目描述 给定四个整数数组 nums1 、 nums2 、 nums3 和 nums4 ，数组长度均为 n 。请计算有多少个元组 (i, j, k, l) 满足： 0 <= i, j, k, l < n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 示例 输入： nums1 = [1, 2] , nums2 = [-2, -1] , nums3 = [-1, 2] , nums4 = [0, 2] 输出： 2 解释： 两个元组为： (0, 0, 0, 1) → 1 + (-2) + (-1) + 2 = 0 (1, 1, 0, 0) → 2 + (-1) + (-1) + 0 = 0 解题过程 步骤 1：暴力法的局限性 最直接的方法是遍历所有四元组（四层循环），检查和是否为 0。时间复杂度为 \(O(n^4)\)，当 \(n=100\) 时计算量已达 \(10^8\)，不可行。 步骤 2：分组优化思路 将四个数组分为两组： 组 A： nums1 和 nums2 ，计算所有可能的和 \(a + b\)。 组 B： nums3 和 nums4 ，计算所有可能的和 \(c + d\)。 问题转化为：找到多少对 (a+b, c+d) 满足 (a+b) + (c+d) = 0 ，即 a+b = -(c+d) 。 步骤 3：哈希表的作用 遍历 nums1 和 nums2 ，用哈希表 map 记录所有 a+b 的值及其出现次数。 例如： nums1=[1,2] , nums2=[-2,-1] ，可能的和包括： 1 + (-2) = -1（出现 1 次） 1 + (-1) = 0（出现 1 次） 2 + (-2) = 0（出现 1 次） 2 + (-1) = 1（出现 1 次） 哈希表： {-1:1, 0:2, 1:1} 遍历 nums3 和 nums4 ，计算 c+d 的值，检查 -(c+d) 是否在哈希表中。若存在，则将对应的出现次数累加到结果中。 例如： nums3=[-1,2] , nums4=[0,2] ，可能的和包括： -1 + 0 = -1 → 需找 -(-1) = 1 ，在哈希表中出现 1 次 → 计数 +1 -1 + 2 = 1 → 需找 -(1) = -1 ，在哈希表中出现 1 次 → 计数 +1 2 + 0 = 2 → 需找 -2 ，不存在 → 忽略 2 + 2 = 4 → 需找 -4 ，不存在 → 忽略 总计数 = 1 + 1 = 2 步骤 4：复杂度分析 时间复杂度：\(O(n^2)\)（两组双层循环）。 空间复杂度：\(O(n^2)\)（哈希表存储最多 \(n^2\) 个键值对）。 关键点 通过分组将问题降维，利用哈希表快速查询互补值，避免暴力枚举。此方法可推广到类似的多数组求和问题（如“两数之和”的扩展）。