【力扣】454. 四数相加 II-Toy模板网

这篇具有很好参考价值的文章主要介绍了【力扣】454. 四数相加 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

454. 四数相加 II

【力扣】454. 四数相加 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

示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：

(0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

提示：
n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
$2^{28}$ <= nums1[i], nums2[i], nums3[i], nums4[i] <= $2^{28}$

题解

这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况。

解题步骤：文章来源地址https://www.toymoban.com/news/detail-587405.html

首先定义一个HashMap，key放a和b两数之和，value 放a和b两数之和出现的次数。
遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
定义int变量result，用来统计 a+b+c+d = 0 出现的次数。
在遍历大C和大D数组，找到如果 0-(c+d) 在 map 中出现过的话，就用 result 把 map 中 key 对应的 value 也就是出现次数统计出来。
最后返回统计值 result

import org.junit.jupiter.api.Test;
import java.util.HashMap;
import java.util.Map;
import static org.junit.jupiter.api.Assertions.assertEquals;

public class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> cnt = new HashMap<>();//key:a+b的数值，value:a+b数值出现的次数

		// 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
        for (int a : nums1) {
            for (int b : nums2) {
                int sum = a + b;
                cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);
            }
        }

        int result = 0;// 统计a+b+c+d = 0 出现的次数
        // 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
        for (int a : nums3) {
            for (int b : nums4) {
                result += cnt.getOrDefault(-(a + b), 0);
            }
        }
        return result;
    }

    @Test
    public void test() {
        Solution s = new Solution();

        assertEquals(2, s.fourSumCount(new int[]{1, 2}, new int[]{-2, -1}, new int[]{-1, 2}, new int[]{0, 2}));
        assertEquals(1, s.fourSumCount(new int[]{0}, new int[]{0}, new int[]{0}, new int[]{0}));
    }
}