LC454. 4Sum II

LC454. 4Sum II

 

 分析:暴力枚举复杂度为$O(n^4)$,不可行。将A,B能组成的和用map计数,查找 -C[i]-D[j] 在map中是否存在

time $O(n^2)$

space $O(n^2)$

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> abSum;
        for (int& a : A)
            for (int&b : B)
                ++abSum[a + b];
        int res = 0;
        for (int& c : C) {
            for (int& d : D) {
                auto it = abSum.find(-c-d);
                if (it != abSum.end())
                    res += it->second;
            }
        }
        return res;
    }
};

 

上一篇:18. 4Sum [Medium]


下一篇:【LeetCode】 18. 4Sum 四数之和(Medium)(JAVA)