文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
4Sum
2. Solutions
- Brute Force
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int length = nums.size();
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for(int i = 0; i < length - 3; i++) {
if(i != 0 && nums[i] == nums[i - 1]) {
continue;
}
for(int j = i + 1; j < length - 2; j++) {
if(nums[j] == nums[j - 1] && j != i + 1) {
continue;
}
for(int k = j + 1; k < length - 1; k++) {
if(nums[k] == nums[k - 1] && k != j + 1) {
continue;
}
for(int l = k + 1; l < length; l++) {
if(nums[l] == nums[l - 1] && l != k + 1) {
continue;
}
int sum = nums[i] + nums[j] + nums[k] + nums[l];
if(sum == target) {
vector<int> temp;
temp.push_back(nums[i]);
temp.push_back(nums[j]);
temp.push_back(nums[k]);
temp.push_back(nums[l]);
result.push_back(temp);
}
}
}
}
}
return result;
}
};
- sort and O(n^3)
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int length = nums.size();
vector<vector<int>> result;
sort(nums.begin(), nums.end());
int sum = 0;
int newTarget = 0;
int left = 0;
int right = 0;
for(int i = 0; i < length - 3; i++) {
if(i != 0 && nums[i] == nums[i - 1]) {
continue;
}
for(int j = i + 1; j < length - 2; j++) {
if(nums[j] == nums[j - 1] && j != i + 1) {
continue;
}
newTarget = target - nums[i] - nums[j];
left = j + 1;
right = length - 1;
while(left < right) {
if(left != j + 1 && nums[left] == nums[left - 1]) {
left++;
continue;
}
if(right < length - 2 && nums[right] == nums[right + 1]) {
right--;
continue;
}
sum = nums[left] + nums[right];
if(sum == newTarget) {
vector<int> temp;
temp.push_back(nums[i]);
temp.push_back(nums[j]);
temp.push_back(nums[left]);
temp.push_back(nums[right]);
result.push_back(temp);
left++;
right--;
}
else if(sum < newTarget) {
left++;
}
else {
right--;
}
}
}
}
return result;
}
};
