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!