分析:暴力枚举复杂度为$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; } };