0454. 四数相加 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 哈希表分组

1. 📝 题目描述

• leetcode

给你四个整数数组 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
• -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

2. 🎯 s.1 - 哈希表分组

c

#define HASH_SIZE 100003
typedef struct Entry { int key; int val; struct Entry* next; } Entry;
Entry* table[HASH_SIZE];

void addVal(int key, int delta) {
    int idx = ((unsigned int)key) % HASH_SIZE;
    for (Entry* e = table[idx]; e; e = e->next)
        if (e->key == key) { e->val += delta; return; }
    Entry* e = (Entry*)malloc(sizeof(Entry));
    e->key = key; e->val = delta; e->next = table[idx]; table[idx] = e;
}

int getVal(int key) {
    int idx = ((unsigned int)key) % HASH_SIZE;
    for (Entry* e = table[idx]; e; e = e->next)
        if (e->key == key) return e->val;
    return 0;
}

int fourSumCount(int* nums1, int nums1Size, int* nums2, int nums2Size,
                 int* nums3, int nums3Size, int* nums4, int nums4Size) {
    memset(table, 0, sizeof(table));
    for (int i = 0; i < nums1Size; i++)
        for (int j = 0; j < nums2Size; j++)
            addVal(nums1[i] + nums2[j], 1);
    int res = 0;
    for (int i = 0; i < nums3Size; i++)
        for (int j = 0; j < nums4Size; j++)
            res += getVal(-nums3[i] - nums4[j]);
    // free
    for (int i = 0; i < HASH_SIZE; i++) {
        Entry* e = table[i];
        while (e) { Entry* t = e; e = e->next; free(t); }
    }
    return res;
}

js

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @param {number[]} nums4
 * @return {number}
 */
var fourSumCount = function (nums1, nums2, nums3, nums4) {
  const map = new Map()
  for (const a of nums1)
    for (const b of nums2) map.set(a + b, (map.get(a + b) || 0) + 1)
  let res = 0
  for (const c of nums3) for (const d of nums4) res += map.get(-c - d) || 0
  return res
}

py

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        ab = Counter(a + b for a in nums1 for b in nums2)
        return sum(ab.get(-c - d, 0) for c in nums3 for d in nums4)

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$

算法思路：

• 将四个数组分为两组，先枯举 AB 两数之和存入哈希表
• 再枯举 CD 两数之和，查找 -(c+d) 在哈希表中的出现次数