标签：数组、中等难度
问题描述
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums 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.
给定整数数组nums和目标值target,判断数组中是否存在元素a,b,c和d使得a+b+c+d=target? 给定目标值target寻找所有的四元组，使得其和为target。
注意: 解集合中不包含重复的四元组。
示例：
给定数组nums = [1, 0, -1, 0, -2, 2], 和目标值target = 0.
解集合是：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
解决方法
方法1：暴力破解法
任选四个元素，判断其值是否为target。
但这里存在一个问题，如果两个解相同，则仅保存一个解，因为题目中要求解集合中不包含重复的四元组。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
vector<int> res;
for(int i = 0; i < nums.size() - 3; i++) {
for(int j = i + 1; j < nums.size() - 2; j++) {
for(int k = j + 1; j < nums.size() - 1; k++) {
for(int m = k + 1; k < nums.size(); m++) {
if (nums[i] + nums[j] + nums[k] + nums[m] == target) {
bool found = false;
res.clear();
res.push_back(i);
res.push_back(j);
res.push_back(k);
res.push_back(m);
for(int n = 0; n < result.size(); n++) {
if (result[i] == res) {
found = true;
break;
}
}
if (found == false)
result.push_back(res);
}
}
}
}
}
return result;
}
};
算法分析：
- 程序中包含5层for循环，时间复杂度接近O(n5)。
- 运行时间：Time Limit Exceeded
方法二：排序法
首先对数组进行排序，接着任选两个数i和j。然后，从两端遍历数组，寻找其和值等于target的端点k和m。由于数组有序，假设A[i]+A[j]+A[k]+A[m]小于target，则将k右移；若其和大于target，则将m左移。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
if(nums.size() < 4)
return result;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size() - 3; i++) {
for(int j = i + 1; j < nums.size() - 2; j++) {
int k = j + 1;
int m = nums.size() - 1;
while (k < m) {
if (nums[i] + nums[j] + nums[k] + nums[m] == target) {
bool found = false;
vector<int> res;
res.push_back(nums[i]);
res.push_back(nums[j]);
res.push_back(nums[k]);
res.push_back(nums[m]);
for(int n = 0; n < result.size(); n++) {
int equal = 0;
for(int p = 0; p < res.size(); p++) {
if(result[n][p] == res[p]) {
equal++;
} else {
break;
}
}
if (equal == 4)found = true;
}
if (found == false) {
result.push_back(res);
}
}
if(nums[i] + nums[j] + nums[k] + nums[m] < target)
k++;
else
m--;
}
}
}
return result;
}
};
算法分析
- 运行时间：72ms
方法三：
对方法二做了一些优化，避免重复元素。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
if(nums.size() < 4)
return result;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size() - 3; i++) {
if(i > 0 && nums[i] == nums[i - 1])
continue;
for(int j = i + 1; j < nums.size() - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1])
continue;
int k = j + 1;
int m = nums.size() - 1;
while (k < m) {
if (nums[i] + nums[j] + nums[k] + nums[m] == target) {
vector<int> res;
res.push_back(nums[i]);
res.push_back(nums[j]);
res.push_back(nums[k]);
res.push_back(nums[m]);
result.push_back(res);
while (k < m && nums[k++] == nums[k]) {}
while (k < m && nums[m--] == nums[m]) {}
}
else if(nums[i] + nums[j] + nums[k] + nums[m] < target) {
while (k < m && nums[k++] == nums[k]) {}
}
else
while (k < m && nums[m--] == nums[m]) {};
}
}
}
return result;
}
};
算法分析
- 时间复杂度约为O(n3)
- 运行时间：52ms
