[LeetCode] 454.四数相加 II（Medium）C语言题解

题目

• 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
• 为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。

---

示例

①示例1

• 输入:
  | A = [ 1, 2]
  | B = [-2,-1]
  | C = [-1, 2]
  | D = [ 0, 2]
• 输出: 2
• 解释: 两个元组如下:
  | 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
  | 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

---

说明

①相关话题

• 哈希表

②相似题目

• 18. 四数之和 — 力扣网
• 18. 4Sum — leetcode

③题目地址

• 454. 四数相加 II — 力扣网
• 454. 4Sum II — leetcode

---

解题方法

①哈希表

• 由于题目对运行速度的要求很高，这里的哈希表直接使用 uthash，节省空间。
• uthash 是一个用 C 语言编写的开源库，使用宏实现了哈希表的增删改查等功能。
• 首先明确题意：这道题与 18. 四数之和 — 力扣网 的区别在于—不同元组的值是可以重复的(下标不同即可)。
• 暴力解法及模仿 18. 四数之和 — 力扣网 的解法 (即将 D 中的元素放入哈希表中，时间复杂度为 O(N^3)) 都会超时。
• 因为不同元组的值可以重复，此时将 -(A[i]+B[j]) 的每一种可能值放入哈希表中，并记录其出现次数，然后两层循环在哈希表中查找是否存在 (C[i]+D[j]) 的每一种可能值，如存在，count += 其出现次数。
• 时间复杂度：O(N^2)。
• 空间复杂度：O(N^2)。

---

代码详解

• 哈希表(uthash)

int fourSumCount(int* A, int ASize, int* B, int BSize, int* C, int CSize, int* D, int DSize) {
    struct hash {
        int value;
        int count;
        UT_hash_handle hh; 
    };
            
    struct hash *hashTable = NULL;    
    int count = 0;
    
    // 将(A[i]+B[j])的每一种可能值放入哈希表中，并记录其出现次数。
    for (int i = 0; i < ASize; i++) {
        for (int j = 0; j < BSize; j++) {
            int n = -A[i]-B[j];            
            struct hash *h;
            HASH_FIND_INT(hashTable, &n, h);
            
            if (!h) {
                h = malloc(sizeof(struct hash));
                h->value = n;
                h->count = 1;
                HASH_ADD_INT(hashTable, value, h);
            }
            else
                h->count++;
        }
    }
    // 在哈希表中查找是否存在(C[i]+D[j])的每一种可能值。
    for (int i = 0; i < CSize; i++) {
        for (int j = 0; j < DSize; j++) {
            int m = C[i]+D[j];
            struct hash *h;
            HASH_FIND_INT(hashTable, &m, h);
                
            if (h)
                count += h->count;
        }
    }
    
    return count;
}

---

附录

• 我的个人博客：messi1002.top
• 如有错误或疑惑之处 请联系 [email protected]
• 所有题目解答：fork me on github