o(n^2logn) time cpp solution


  • 0
    H
    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;
    	}
    };
    

Log in to reply
 

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