四数相加 II

发布时间:2024年01月23日

题目链接

四数相加 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;
    }
}

关键点

文章来源:https://blog.csdn.net/weixin_51628158/article/details/135746764
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。