# o(n^2logn) time cpp solution

• class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
vector<int> AB;
vector<int> CD;
for (int i = 0; i < A.size(); i++)
for (int j = 0; j < B.size(); j++)
AB.push_back(A[i] + B[j]);
for (int i = 0; i < C.size(); i++)
for (int j = 0; j < D.size(); j++)
CD.push_back(C[i] + D[j]);
if (AB.size() == 0 || CD.size() == 0)
return 0;
sort(AB.begin(), AB.end());
sort(CD.begin(), CD.end());
vector<pair<int, int>> ABp;
vector<pair<int, int>> CDp;
int t = AB[0];
int count = 1;
for (int i = 1; i < AB.size(); i++) {
if (AB[i] == t)
count++;
else {
ABp.push_back(pair<int, int>(t, count));
t = AB[i];
count = 1;
}
}
ABp.push_back(pair<int, int>(t, count));
t = CD[0];
count = 1;
for (int i = 1; i < CD.size(); i++) {
if (CD[i] == t)
count++;
else {
CDp.push_back(pair<int, int>(t, count));
t = CD[i];
count = 1;
}
}
CDp.push_back(pair<int, int>(t, count));
int j = ABp.size() - 1, i = 0;
int ans = 0;
while (i < CDp.size() && j >= 0) {
int m = -CDp[i].first;
if (m < ABp[j].first)
j--;
else if (m > ABp[j].first)
i++;
else {
ans += CDp[i].second*ABp[j].second;
i++;
j--;
}
}
return ans;
}
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.