[LeetCode]4Sum

和3Sum的解法仍然是十分类似的，我们先reduce成3Sum，继续reduce成2Sum的问题。2Sum的话我们就可以用two pointer或者hashmap来做，去重的思路仍然是类似的，这里我们用two pointer，时间复杂度O(N^3)，常数空间。代码如下：

	class Solution {
	public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
	int len = nums.size();
	sort(nums.begin(), nums.end());
	vector<vector<int>> res;
	for (int a = 0; a < len; ++a)
	{
	if (a && nums[a] == nums[a - 1])continue;
	for (int b = a + 1; b < len - 2; ++b)
	{
	if (b > a + 1 && nums[b] == nums[b - 1])continue;
	int i = b + 1, j = len - 1;
	while (i < j)
	{
	int sum = target - (nums[a] + nums[b]);
	if (nums[i] + nums[j] < sum)++i;
	else if (nums[i] + nums[j] > sum)--j;
	else
	{
	res.push_back({nums[a], nums[b], nums[i++], nums[j--]});
	while (i < j && nums[i] == nums[i - 1])++i;
	while (i < j && nums[j] == nums[j + 1])--j;
	}
	}
	}
	}
	return res;
	}
	};

view raw 4Sum_two_pointer.cpp hosted with ❤ by GitHub

除此之外我们还可以reduce成两个two sum的问题。但这样去重会有点麻烦，我们需要用hashmap去重，具体请参考代码里的注释。时间复杂度O(k * N^2)，k为每个sum对应的list的平均长度。代码如下：

	struct Hasher
	{
	size_t operator()(const vector<int>& input)const
	{
	string str;
	for (auto& num : input)str += to_string(num) + ",";
	return hash<string>()(str);
	}
	};
	class Solution {
	public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
	int len = nums.size();
	if (len < 4)return{};
	sort(nums.begin(), nums.end());
	unordered_set<vector<int>, Hasher> res;
	unordered_map<int, unordered_set<vector<int>, Hasher>> sums;
	sums[nums[0] + nums[1]].insert({ nums[0], nums[1] });
	for (int i = 2; i < len - 1; ++i)
	{
	//we can't skip here, for example [-1, 0, 0, -1], target = 0
	//we will miss[-1, 0, 0, 1] in this case]
	//but that will also cause other issus in case [-2, -1, 0, 0, 3], target = 0
	//we will have duplicated [-2, -1, 0, 3], so we have to use set to remove duplicate results
	//if (nums[i] == nums[i - 1])continue;
	for (int j = i + 1; j < len; ++j)
	{
	int sum = nums[i] + nums[j];
	if (sums.find(target - sum) != sums.end())
	{
	for (const auto& v : sums[target - sum])
	{
	res.insert({ v[0], v[1], nums[i], nums[j] });
	}
	while (j < len - 1 && nums[j] == nums[j + 1])++j;
	}
	}
	//update sums
	for (int k = 0; k < i; ++k)
	{
	if (k && nums[k] == nums[k - 1])continue;
	int sum = nums[k] + nums[i];
	sums[sum].insert({nums[k], nums[i]});
	}
	}
	vector<vector<int>> vs;
	for (auto v : res)vs.push_back(v);
	return vs;
	}
	};

view raw 4Sum_2_two_sum.cpp hosted with ❤ by GitHub

我们可以generalize K sum问题的解决办法，即一步一步reduce成2sum的问题，用dfs即可。时间复杂度O(N^(k - 1))。代码如下：

	class Solution {
	public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
	int len = nums.size();
	//make sure the result is sorted from smaller to larger
	sort(nums.begin(), nums.end(), greater<int>());
	return KSum(nums, target, 4, 0);
	}
	private:
	vector<vector<int>> KSum(const vector<int>& nums, int target, int k, int start)
	{
	int len = nums.size();
	if (len - start < k)return{};
	if (k == 2)
	{
	vector<vector<int>> res;
	int lo = start, hi = len - 1;
	while (lo < hi)
	{
	int sum = nums[lo] + nums[hi];
	if (sum < target)--hi;
	else if (sum > target)++lo;
	else
	{
	res.push_back({ nums[hi], nums[lo] });
	while (lo < hi && nums[lo] == nums[lo + 1])++lo;
	while (lo < hi && nums[hi] == nums[hi - 1])--hi;
	++lo;
	--hi;
	}
	}
	return res;
	}
	else
	{
	vector<vector<int>> res;
	for (int i = start; i < len - k + 1; ++i)
	{
	if (i > start && nums[i] == nums[i - 1])continue;
	auto lists = KSum(nums, target - nums[i], k - 1, i + 1);
	for (auto& list : lists)
	{
	list.push_back(nums[i]);
	res.push_back(list);
	}
	}
	return res;
	}
	}
	};

view raw 4Sum_k_sum.cpp hosted with ❤ by GitHub