| 2024-04-18 |

# 四数相加 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：
1
2
3
4
5
6
输入：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
示例 2：
1
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

-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

这道题目的关键在于决定哈希表里面 Key 和 Value 的关系

我一开始想着存 0-n 的索引 index 和 nums1 2 和 Sum 之间的关系发现没有必要

看完题解后明白判断重复出现的时候必须 Key Value 有一方为 出现次数 这点很重要

# 题解

public class Solution {
    public int FourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int n;
        n = nums1.Length;
        int result = 0;
        Dictionary<int,int> sum12Dic = new();  // nums1和nums2的和  出现次数
        for(int i= 0;i<n;i++){
            for(int j= 0 ;j<n;j++){
                int sum = nums1[i] + nums2[j];
                if(sum12Dic.ContainsKey(sum)){
                    sum12Dic[sum]++;  
                }else{
                    sum12Dic[sum] = 1;
                }
            }
        }
        for(int i= 0;i<n;i++){
            for(int j= 0 ;j<n;j++){
                int sum = nums3[i]+nums4[j];
                //遍历字典
                if(sum12Dic.TryGetValue(-sum,out int value)){
                     result += value;
                }
            }
        }
        
        return result;

    }
}

# 标答

public int FourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
       Dictionary<int, int> dic = new Dictionary<int, int>();
        foreach(var i in nums1){
            foreach(var j in nums2){
                int sum = i + j;
                if(dic.ContainsKey(sum)){
                    dic[sum]++;
                }else{
                    dic.Add(sum, 1);
                }
                
            }
        }
        int res = 0;
         foreach(var a in nums3){
            foreach(var b in nums4){
                int sum = a+b;
                if(dic.TryGetValue(-sum, out var result)){
                    res += result;
                }
            }
        }
        return res;
    }

C++:

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> umap; //key:a+b的数值，value:a+b数值出现的次数
        // 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
        for (int a : A) {
            for (int b : B) {
                umap[a + b]++;
            }
        }
        int count = 0; // 统计a+b+c+d = 0 出现的次数
        // 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
        for (int c : C) {
            for (int d : D) {
                if (umap.find(0 - (c + d)) != umap.end()) {
                    count += umap[0 - (c + d)];
                }
            }
        }
        return count;
    }
};

tags: #算法