四数相加

发表于 更新于 分类于

算法-四数相加

背景

  • 算法–四数相加

  • 博主以代码随想录算法公开课进行学习

题目

  • 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

    为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

    例如:

    输入:

    • A = [ 1, 2]
    • B = [-2,-1]
    • C = [-1, 2]
    • D = [ 0, 2]

    输出:

    2

    解释:

    两个元组如下:

    1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
    2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

思路

  • 定义一个哈希map，key放a和b俩数之和，value放a和b俩数和出现的次数
  • 遍历A、B数组，统计两数和和出现次数
  • 再遍历C、D数组、找到0-（c+d）在map中出现，count+value（value即出现的次数）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int r = 0;
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i : nums1){
            for(int j : nums2){
                int sum = i + j;
                map.put(sum,map.getOrDefault(sum,0) + 1);
            }
        }
        for(int i : nums3){
            for(int j : nums4){
                r += map.getOrDefault(0 - i - j,0);
            }
        }
        return r;
    }
}

总结

  • getOrDefault 核心作用：简化 Map 中 “获取值 + 处理键不存在” 的逻辑，避免手动判断 containsKey。
    • 尝试从 Map 中获取指定 key 对应的 value；
    • 如果 key 存在，返回对应的 value；
    • 如果 key 不存在，返回你指定的 defaultValue（默认值）。
  • 语法规则：map.getOrDefault(键, 默认值)，返回值类型和 “默认值” 类型一致（比如键是 Integer，默认值也得是 Integer）。
  • 典型场景：计数统计（如四数相加的次数统计）、避免空值（NPE）、默认值兜底等。
  • 关键逻辑：利用 a + b + c + d = 0 等价于 a + b = -(c + d)，通过哈希表快速匹配目标值。