454 四数相加 II

本文最后更新于：2022年8月30日 晚上

给定四个包含整数的数组列表 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
2
3
4
5
6
7
8
9
10
11
12
13
输入:
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

Solution

  • 哈希表
  • 暴力解法 O(n^4^) ，超时
  • 方案一：对 C 和 D 建立求和哈希表
  • 方案二：对 A 和 B，C 和 D 分别建立求和哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// @lc code=start
class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> hashtable;
        for(int i=0;i<C.size(); ++i){
            for(int j=0; j<D.size(); ++j){
                hashtable[C[i]+D[j]] += 1;
            }
        }
        int res = 0;
        for(int i=0;i<A.size();++i)
            for(int j=0; j<B.size(); ++j)
                if(hashtable.find(-A[i]-B[j]) != hashtable.end())
                    res+=hashtable[-A[i]-B[j]];
        return res;
    }
};
// @lc code=end

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map1 = new HashMap<>();
        Map<Integer, Integer> map2 = new HashMap<>();

        for (int n1 : nums1) {
            for (int n2 : nums2) {
                int tmp = n1 + n2;
                if (map1.containsKey(tmp)) {
                    map1.put(tmp, map1.get(tmp) + 1);
                } else {
                    map1.put(tmp, 1);
                }
            }
        }

        for (int n3 : nums3) {
            for (int n4 : nums4) {
                int tmp = n3 + n4;
                if (map2.containsKey(tmp)) {
                    map2.put(tmp, map2.get(tmp) + 1);
                } else {
                    map2.put(tmp, 1);
                }
            }
        }

        int res = 0;
        for (int n1 : map1.keySet()) {
            for (int n2 : map2.keySet()) {
                if (n1 + n2 == 0) {
                    res += map1.get(n1) * map2.get(n2);
                }
            }
        }
        return res;
    }
}
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！