哈希表|434.四数相加II

力扣题目链接

struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};

int fourSumCount(int* A, int ASize, int* B, int BSize, int* C, int CSize, int* D, int DSize) {
    struct hashTable* hashtable = NULL;
    for (int i = 0; i < ASize; ++i) {
        for (int j = 0; j < BSize; ++j) {
            int ikey = A[i] + B[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 < CSize; ++i) {
        for (int j = 0; j < DSize; ++j) {
            int ikey = -C[i] - D[j];
            struct hashTable* tmp;
            HASH_FIND_INT(hashtable, &ikey, tmp);
            if (tmp != NULL) {
                ans += tmp->val;
            }
        }
    }
    return ans;
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/4sum-ii/solutions/499745/si-shu-xiang-jia-ii-by-leetcode-solution/

卡哥没有c语言的题解

不知道怎样搞一个哈希表出来？

一、出错点

1.关于c语言没有map，如何创建哈希表解题呢？

2.一些函数不认识，不会用

二、理解后的思路

我们可以将四个数组分成两部分，AAA 和 BBB 为一组，CCC 和 DDD 为另外一组。

对于 AAA 和 BBB，我们使用二重循环对它们进行遍历，得到所有 A[i]+B[j]A[i]+B[j]A[i]+B[j] 的值并存入哈希映射中。对于哈希映射中的每个键值对，每个键表示一种 A[i]+B[j]A[i]+B[j]A[i]+B[j]，对应的值为 A[i]+B[j]A[i]+B[j]A[i]+B[j] 出现的次数。

对于 CCC 和 DDD，我们同样使用二重循环对它们进行遍历。当遍历到 C[k]+D[l]C[k]+D[l]C[k]+D[l] 时，如果 −(C[k]+D[l])-(C[k]+D[l])−(C[k]+D[l]) 出现在哈希映射中，那么将 −(C[k]+D[l])-(C[k]+D[l])−(C[k]+D[l]) 对应的值累加进答案中。

最终即可得到满足 A[i]+B[j]+C[k]+D[l]=0A[i]+B[j]+C[k]+D[l]=0A[i]+B[j]+C[k]+D[l]=0 的四元组数目。

对，就是用两个嵌套for循环！