leetcode 454. 4Sum II 四个数求和的总次数+Map降低运算复杂度

谁践踏了优雅 2022-06-04 09:05 116阅读 0赞

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A\[i\] + B\[j\] + C\[k\] + D\[l\] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

Input:  
A = \[ 1, 2\]  
B = \[-2,-1\]  
C = \[-1, 2\]  
D = \[ 0, 2\]

Output:  
2

Explanation:  
The two tuples are:  
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

题意很几简单，应该使用map来做标记来降低复杂度，嗯嗯，很不错的题，直接遍历肯定超时。

建议和这一道题[leetcode 18. 4Sum KSum的解决办法][leetcode 18. 4Sum KSum] 一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) 
        {
            int target = 0;
            map<int, int> abSum;
            for (int a : A)
            {
                for (int b : B)
                {
                    abSum[a + b]++;
                }
            }
    
            int count = 0;
            for (int c : C)
            {
                for (int d : D)
                {
                    if (abSum.find(target - c - d) != abSum.end())
                        count += abSum[target - c - d];
                }
            }
            return count;
        }
    };

[leetcode 18. 4Sum KSum]: http://blog.csdn.net/jackzhang_123/article/details/77747890