四数相加 II

题目链接

四数相加 II

题目描述

注意点

• 四个数组长度都是n
• 满足nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
• 1 <= n <= 200

解答思路

• 可以将nums1和nums2分为一组，nums3和nums4分为一组，计算每组任意两个数字相加的组合以及每种组合的数量存在哈希表中，再计算两组中数字相加为0的组合数量就是结果
• nums3和nums4分为一组可以不用哈希表存储该组中两个数字相加的组合以及每种组合的数量，可直接根据相加的组合去nums1和nums2分为一组的哈希表中查找与之相对的组合数量（也就是0 - num3 - num4），其能保证num1 + num2 + num3 + num4 = 0

代码

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                map.put(num1 + num2, map.getOrDefault(num1 + num2, 0) + 1);
            }
        }
        for (int num3 : nums3) {
            for (int num4 : nums4) {
                if (map.get(-num3 - num4) != null) {
                    res += map.get(-num3 - num4);
                }
            }
        }
        return res;
    }
}

关键点

• 无