454.四个数相加II

题目描述

给你四个整数数组 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
```

-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

题解

思路： 此题总的有四个数组，我们可以先对两个两个的数组进行处理，也就是处理nums1和nums2的每种相加情况，将每种情况的结果存在map1中，相加结果作为key，结果出现的次数作为value。对nums3和nums4做同样的处理后将结果存在map2中。接下来的操作就类似于1. 两数之和

代码(C++版本)：

unordered_map<int, int> twoSum(vector<int>& nums1, vector<int>& nums2){
    unordered_map<int, int> map;
    for (int i = 0; i < nums1.size(); i++){
        for (int j = 0; j < nums2.size(); j++){
            int count = 1;
            int sum = nums1[i];
            sum += nums2[j];
            auto iter = map.find(sum);
            if (iter != map.end()) {
                iter->second++;
            }else {
                map.insert(pair<int, int>(sum,count));
            }
        }
    }
    return map;
}

int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    unordered_map<int, int> map1 = twoSum(nums1, nums2);
    unordered_map<int, int> map2 = twoSum(nums3, nums4);
    int result = 0;
    auto iter1 = map1.begin();
    while (iter1 != map2.end()) {
        int tmp = 0 - iter1->first;
        auto iter2 = map2.find(tmp);
        if (iter2 != map2.end()) {
            result += iter1->second * iter2->second;
        }
        iter1++;
    }
    return result;
}

分析：时间复杂度为O(N^2); 空间复杂度为O(2N)

官方-题解

备注： 和我的思路一样，但这个代码更简洁

代码(C++版本)：

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
    unordered_map<int, int> countAB;
    for (int u: A) {
        for (int v: B) {
            ++countAB[u + v];
        }
    }
    int ans = 0;
    for (int u: C) {
        for (int v: D) {
            if (countAB.count(-u - v)) {
                ans += countAB[-u - v];
            }
        }
    }
    return ans;
}

代码随想录-题解

备注： 和我的思路一样，但这个代码更简洁

代码(C++版本)：

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
    unordered_map<int, int> umap; //key:a+b的数值，value:a+b数值出现的次数
    // 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
    for (int a : A) {
        for (int b : B) {
            umap[a + b]++;
        }
    }
    int count = 0; // 统计a+b+c+d = 0 出现的次数
    // 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
    for (int c : C) {
        for (int d : D) {
            if (umap.find(0 - (c + d)) != umap.end()) {
                count += umap[0 - (c + d)];
            }
        }
    }
    return count;
}