徐州智能模板建站,做旅游攻略的网站好,济南网站优化推广公司,永州市网站建设题目来源#xff1a; leetcode题目#xff0c;网址#xff1a;15. 三数之和 - 力扣#xff08;LeetCode#xff09;
解题思路#xff1a; 1.三重循环暴力遍历#xff0c;超时原因#xff0c;三重循环复杂度太高 2.双重循环哈希表#xff0c;超时原因#xff0c;哈…题目来源 leetcode题目网址15. 三数之和 - 力扣LeetCode
解题思路 1.三重循环暴力遍历超时原因三重循环复杂度太高 2.双重循环哈希表超时原因哈希表无法判断是否重复需要暴力遍历从而导致超时 3.双指针。固定第一个数的值
解题代码
//暴力遍历超时
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint res;sort(nums.begin(),nums.end());if(nums[0]0 || nums[nums.size()-1]0){return res;}for(int i0;inums.size();i){for(int ji1;jnums.size();j){int sum2nums[i]nums[j];if(sum20){break;}for(int kj1;knums.size();k){int sum3nums[k]sum2;vectorint temp{nums[i],nums[j],nums[k]};if(sum30){if(res.size()!0 contains(res,temp)){continue;}res.push_back(temp);}}}}return res;}bool contains(vectorvectorint res,vectorint temp){for(int ires.size()-1;i0;i--){if(res[i][0]!temp[0]){break;}if(res[i][1]temp[1] res[i][2]temp[2]){return true;} }return false;}
};
//双重循环哈希表超时
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint res;sort(nums.begin(),nums.end());unordered_mapint,int map;for(int i0;inums.size();i){map[nums[i]]map[nums[i]]1;} for(int i0;inums.size() nums[i]0;i){map[nums[i]]--;unordered_mapint,int newMapmap;for(int jnums.size()-1;ji nums[j]0;j--){newMap[nums[j]]--;if(newMap[-nums[i]-nums[j]]0){vectorint temp{nums[i],-nums[i]-nums[j],nums[j]};if(!contains(res,temp)){res.push_back(temp);}}}}return res;}bool contains(vectorvectorint res,vectorint temp){//res中是否包含tempfor(int ires.size()-1;i0;i--){if(res[i][0]temp[0] res[i][1]temp[1] res[i][2]temp[2]){return true;} }return false;}
};
//双指针
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint res;sort(nums.begin(),nums.end());for(int i0;inums.size();i){if(i!0 nums[i]nums[i-1]){continue;}int target0-nums[i];int lefti1;int rightnums.size()-1;while(leftright){if(nums[left]nums[right]target){vectorint temp{nums[i],nums[left],nums[right]};res.push_back(temp);left;right--;while(leftright nums[left]nums[left-1]){//放在if外是需要增加 left!(i1)的判断否则形如 -1,-1,2 的结果会被跳过left;}while(leftright nums[right]nums[right1]){right--;} }else if(nums[left]nums[right]target){left; }else{right--; }}}return res;}
};
总结 没通过看官方题解的。
