4Sum II

发表于 | 分类于

4Sum II

题目描述：

给定4个数字数组，要求分别从4个数组中各取一个数的组合中和为0的情况有多少种。

例子：

具体描述见[LeetCode454]

解题思路：

主要的思路是利用哈希表；我们取其中两个数组，然后利用其和为key，出现的次数为value构建哈希表；对剩下的两个数组也进行相同的操作；然后遍历第一个哈希表，在第二个哈希表中找到是否能够构成0的值；如果存在则对其次数进行乘积操作加到结果上。

代码如下：

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
class Solution {
public:
    void fillMap(vector<int> &A, vector<int> &B, map<int, int> &m){
        for (int i = 0; i < A.size(); i++){
            for (int j = 0; j < B.size(); j++){
                m[A[i] + B[j]]++;
            }
        }//和为key;出现次数为value
    }
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        map<int, int> m1;
        map<int, int> m2;
        
        fillMap(A, B, m1);
        fillMap(C, D, m2);
        int res = 0;
        
        for (auto it1 = m1.begin(); it1 != m1.end(); it1++){
            
            auto it2 = m2.find(-it1->first);
            //此处注意负号，即要求和为0
            if (it2 != m2.end()){
                res += it1->second * it2->second;
                //出现的次数的乘积
            }
        }
        return res;
    }
};