LeetCode454. 四数相加 II

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
1
2
3
4
5
6

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1
1
2

思路

• nums1和nums2为一组A，nums3和nums4划分为一组B
• 用两个for循环，把A中两个数组之和sum、以及sum出现的次数，存到 unordered_map里，B同理
• 遍历A数组，查找B中是否有匹配值，计算次数

代码

使用multiset法会超出时间限制

#include <unordered_set>
using namespace std;
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3,
                     vector<int>& nums4) {
        int count = 0;
        int size = nums1.size();
        unordered_multiset<int> set12;
        unordered_multiset<int> set34;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                set12.emplace(nums1[i] + nums2[j]);
                set34.emplace(nums3[i] + nums4[j]);
            }
        }
        for (auto it = set12.begin(); it != set12.end(); it++) {

            count += set34.count(0 - *it);
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

原因是multiset底层实现是红黑树，查找效率不如哈希

使用unordered_map

#include <unordered_map>
using namespace std;
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3,
                     vector<int>& nums4) {
        int count = 0;
        int size = nums1.size();
        unordered_map<int, int> map12; //(值，次数)
        unordered_map<int, int> map34;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                auto it12 = map12.find(nums1[i] + nums2[j]);
                if (it12 != map12.end()) {
                    it12->second++;
                } else {
                    map12.insert(pair<int, int>(nums1[i] + nums2[j], 1));
                }

                auto it34 = map34.find(nums3[i] + nums4[j]);
                if (it34 != map34.end()) {
                    it34->second++;
                } else {
                    map34.insert(pair<int, int>(nums3[i] + nums4[j], 1));
                }
            }
        }
        for (auto it12 = map12.begin(); it12 != map12.end(); it12++) {

            auto it34 = map34.find(0 - it12->first);
            if (it34 != map34.end()) {
                count = count + it12->second * it34->second;
            }
        }
        return count;
    }
};
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