LeetCode 4Sum

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]
]

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;
}
};


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;
}
};


One thought on “LeetCode 4Sum”

1. Pingback: LeetCode 4Sum II | bitJoy > code