LeetCode Teemo Attacking

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

本题问一个数组中哪四个数加起来的和等于target，相当于LeetCode 3Sum的升级版，但是方法和3Sum是一样的，先枚举前两个数，对于后两个数，用首尾指针来求和。

一开始我的代码完全按照LeetCode 3Sum来写，先求最大最小值，然后用桶来hash，最后三层循环，代码如下：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
    	int min_v = INT_MAX, max_v = INT_MIN;
    	for(int i = 0; i < nums.size(); ++i) {
    		if(nums[i] < min_v)min_v = nums[i];
    		if(nums[i] > max_v)max_v = nums[i];
    	}
    	vector<int> hash(max_v - min_v + 1, 0);
    	for(int i = 0; i < nums.size(); ++i){
    		++hash[nums[i] - min_v];
    	}
    	vector<vector<int>> ans;
    	for(int i = 0; i < hash.size(); ++i){
    		if(hash[i] == 0)continue;
    		--hash[i];
    		for(int j = i; j < hash.size(); ++j){
    			if(hash[j] == 0) continue;
    			--hash[j];
    			int u = j, v = hash.size() - 1;
    			while(u <= v){
    				while(u <= v && hash[u] == 0) ++u;
    				if(u > v) break;
    				--hash[u];
    				while(u <= v && hash[v] == 0) --v;
    				if(u > v){
    					++hash[u];
    					break;
    				}
    				--hash[v];

    				int sum = i + j + u + v + 4 * min_v;
    				++hash[u];
    				++hash[v];
    				if(sum == target){
    					ans.push_back({i + min_v, j + min_v, u + min_v, v + min_v});
    					++u;
    					--v;
    				} else if(sum < target) ++u;
    				else --v;
    			}
    			++hash[j];
    		}
    		++hash[i];
    	}
    	return ans;
    }
};

但是本代码提交TLE，看了一下，最后一个样例中，最小值有-236727523之小，最大值有91277418之大，导致hash数组太大了，从而无效的空for循环太多，最终TLE。

后来改用排序代替hash，需要注意为了防止重复结果，对四个数都要有去重的操作。代码如下：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
    	sort(nums.begin(), nums.end());
    	vector<vector<int>> ans;
    	int n = nums.size();
    	for(int i = 0; i < n - 3; ++i){
    		if(i > 0 && nums[i] == nums[i-1])continue; // 防止nums[i]重复
    		for(int j = i + 1; j < n - 2; ++j){
    			if(j > i + 1 && nums[j] == nums[j-1])continue; // 防止nums[j]重复
    			int u = j + 1, v = n - 1;
    			while(u < v){
    				int sum = nums[i] + nums[j] + nums[u] + nums[v];
    				if(sum == target){
    					ans.push_back({nums[i], nums[j], nums[u], nums[v]});
    					int k = u + 1;
    					while(k < v && nums[k] == nums[u]) ++k; // 防止nums[u]重复
    					u = k;
    					k = v - 1;
    					while(k > u && nums[k] == nums[v]) --k; // 防止nums[v]重复
    					v = k;
    				}
    				else if(sum < target) ++u;
    				else --v;
    			}
    		}
    	}
    	return ans;
    }
};

本代码提交AC，用时39MS。

还有一种思路是，先对数组中两数之和Hash，然后枚举两个两数之和，转换为类似Two Sum的方法，时间复杂度为$O(n^2)$。