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] ]
博主的答案最后是TLE，虽然代码正确，但是算法耗时太长，算法复杂度为O(N^4)，以下是博主代码：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<int> array;
vector<int> array_target;
vector<vector<int>> result;
vector<vector<int>> finish;
std::sort(nums.begin(), nums.end());
if(nums.size() < 4) return finish;
//array = reduceCheck(nums);
array = nums;
for(int i = 0; i < array.size()-3; i++){
for(int j = i+1; j < array.size()-2; j++){
for(int k = j+1; k < array.size()-1; k++){
for(int l = k+1; l < array.size(); l++){
array_target.clear();
if(target == (array[i] + array[j] + array[k] + array[l])){
array_target.push_back(array[i]);
array_target.push_back(array[j]);
array_target.push_back(array[k]);
array_target.push_back(array[l]);
result.push_back(array_target);
}
}
}
}
}
finish = CheckSame(result);
return finish;
}
protected:
vector<vector<int>> CheckSame(vector<vector<int>>& array){
vector<vector<int>> result;
for(int i = 0; i < array.size(); i++){
if (i==0){
result.push_back(array[i]);
continue;
}
bool flag = false;
for(int j = 0; j < i; j++){
if(array[i] == array[j]){
flag = true;
break;
}
}
if(flag == false){
result.push_back(array[i]);
}
}
return result;
}
};
是的，博主在写代码时没有考虑算法复杂度的问题，并且对一些技巧不太了解，下面就来解析一个算法复杂度为O(N^3)的代码：
/**
* 本代码由九章算法编辑提供。没有版权欢迎转发。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，九章强化班，Java入门与基础算法班
* - 更多详情请见官方网站：http://www.jiuzhang.com/
*/
class Solution {
public:
/*
题意：找到数列中所有和等于目标数的四元组，需去重
多枚举一个数后，参照3Sum的做法，O(N^3)
*/
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int len = nums.size();
int left, right, sum;
sort(nums.begin(), nums.end());
vector<vector<int>> res;
vector<int> tmp;
for (int i = 0; i < len - 3; i++) {
if (i && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < len - 2; j++) {
if (j != i + 1 && nums[j] == nums[j - 1]) continue;
sum = target - nums[i] - nums[j];
left = j + 1;
right = len - 1;
while (left < right) {
if (nums[left] + nums[right] == sum) {
tmp.clear();
tmp.push_back(nums[i]);
tmp.push_back(nums[j]);
tmp.push_back(nums[left]);
tmp.push_back(nums[right]);
res.push_back(tmp);
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else
if (nums[left] + nums[right] > sum) right--;
else left++;
}
}
}
return res;
}
};
确实比博主的代码简洁多了，下面介绍其中的一些技巧：
1.nums在使用前进行排序
★2.通过相邻相等的判断，实现了相同答案的滤除
★3.在降低算法复杂度方面，从一个数组中取出四个数的方法，先从其中取出两个，都是从左向右，后两个数如果也这样取，那就是O(N^4)，所以以下代码至关重要：
left = j + 1;
right = len - 1;
while (left < right) {
if (nums[left] + nums[right] == sum) {
tmp.clear();
tmp.push_back(nums[i]);
tmp.push_back(nums[j]);
tmp.push_back(nums[left]);
tmp.push_back(nums[right]);
res.push_back(tmp);
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else
if (nums[left] + nums[right] > sum) right--;
else left++;
}
注意这个if、else，我们要处理的问题是固定和，如果已经有一个答案了，那么原先的基础上的两个值都要改变，不能只改变一个，如果目前没有答案，那我们只改变其中一个值，直到遇到答案，这里有一个大小相对变化的问题，不用担心漏掉，这样就把算法复杂度降低了一个数量级O(N^3)。
总体来说，就是将两个数确定下来之后，剩下的是一个定和问题，从而使用低算法复杂度的算法。当然，这份代码效率也并不是很高，还有其它更快的算法，比较常见的是使用hash表，还有其它另人瞠目的算法，无奈博主水平有限，以后有机会再介绍吧。
OK，See You Next Chapter!