力扣454.四数相加Ⅱ

给你四个整数数组 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
解释：
两个元组如下：
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：

输入：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

题目分析

这道题给了我们俩个数组，让我们找出nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0共有几组，关于存在性的问题我们很快就能想到哈希表。

解题思路

我们先把四个数组分成俩组，第一组和第二组中的所有元素俩俩相加得到的值存入哈希表中，而他们相加的值为键，对应的值便是出现次数，

​
 int ikey = nums1[i] + nums2[j];
            struct hashTable* tmp;
            HASH_FIND_INT(hashtable, &ikey ,tmp);
            if(tmp == NULL) {
                struct hashTable* tmp = malloc(sizeof(struct hashTable));
                tmp->key = ikey;
                tmp->val = 1;
                HASH_ADD_INT(hashtable,key,tmp);
            }else {
                tmp->val++;
            }
        }

​

我们通过上面的代码判断，如果出现过，所对应的值‘+1，如果返回NULL说明没有出现过，对应值为1。这样我们就得到了储存着num1num2相加数据的哈希表，我们再与剩下俩个数组相加得到的值对比，如果他们俩相加的相反数在哈希表中存在，便对应nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0再看他对应的次数，即得出答案。

struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};
int fourSumCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* nums3, int nums3Size, int* nums4, int nums4Size) {
    struct hashTable* hashtable = NULL;
    for(int i = 0;i < nums1Size;++i) {
        for(int j = 0;j< nums2Size;j++) {
            int ikey = nums1[i] + nums2[j];
            struct hashTable* tmp;
            HASH_FIND_INT(hashtable, &ikey ,tmp);
            if(tmp == NULL) {
                struct hashTable* tmp = malloc(sizeof(struct hashTable));
                tmp->key = ikey;
                tmp->val = 1;
                HASH_ADD_INT(hashtable,key,tmp);
            }else {
                tmp->val++;
            }
        }
    }
    int ans = 0;
    for(int i = 0;i<nums3Size;i++){
        for(int j =0;j<nums4Size;j++){
            int ikey = -nums3[i]-nums4[j];
            struct hashTable* tmp;
            HASH_FIND_INT(hashtable,&ikey,tmp);
            if(tmp != NULL) {
                ans += tmp->val;
            }
        }
    }
    return ans;
}