力扣454 四数相加

标签：map 四数 int 454 力扣 nums4 nums1 nums2 nums3

题目：

给四个整数数组 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
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

思路：

1.首先定义 一个map，key放a和b两数之和，value 放a和b两数之和出现的次数。

2.遍历A和B数组，统计两个数组元素之和，和出现的次数，放到map中。

3.遍历C和D数组，找到如果 0-(c+d) 在map中出现过的话，就用sum把map中key对应的value也就是出现次数统计出来。

5.最后返回统计值 sum就可以了。

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int sum=0,temp=0;//sum为满足要求的元组个数，temp记录0-(C+D)
        int sum1=0,sum2=0;//A+B,C+D
        Map<Integer, Integer> map = new HashMap<>();
        int n=nums1.length;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                sum1=nums1[i]+nums2[j];//A+B
                if(map.containsKey(sum1)){//如果A+B之前出现过，那么记录多一次
                    map.put(sum1,map.get(sum1)+1);
                }else{
                    map.put(sum1,1);//没出现过，就是第一次
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                sum2=nums3[i]+nums4[j];
                temp=0-sum2;//0-(C+D)
                if(map.containsKey(temp)){//如果map中出现过能满足temp的A+B组合
                    sum+=map.get(temp);//sum加A+B所有组合可能的次数
                }
            }
        }
        return sum;
    }
}

 

标签：map,四数,int,454,力扣,nums4,nums1,nums2,nums3
From： https://www.cnblogs.com/cjhtxdy/p/16928460.html