[LeetCode]4Sum

这道题和4Sum十分的类似，我们可以reduce成3Sum的问题，但是鉴于这道题只需要我们求数量，我们可以reduce成两个2Sum的问题，这样只需要O(N^2)的时间我们就可以解决这个问题。代码如下：

	class Solution {
	public:
	int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
	unordered_map<int, int> map;
	int res = 0;
	for (int i = 0; i < A.size(); ++i)
	{
	for (int j = 0; j < B.size(); ++j)
	{
	int sum = A[i] + B[j];
	++map[sum];
	}
	}
	for (int i = 0; i < C.size(); ++i)
	{
	for (int j = 0; j < D.size(); ++j)
	{
	int sum = C[i] + D[j];
	res += map[-sum];
	}
	}
	return res;
	}
	};

view raw 4Sum II.cpp hosted with ❤ by GitHub