网站模版 带 手机版,做网站视频一般上传到哪里,仿制app软件多少钱,广西省住房和城乡建设厅官网文章目录 一、[题目链接#xff1a;三数之和](https://leetcode.cn/problems/3sum/submissions/515727749/)二、思路讲解三、代码演示 先赞后看#xff0c;养成习惯#xff01;#xff01;#xff01;^ _ ^3 ❤️ ❤️ ❤️ 码字不易#xff0c;大家的支持就是我坚持… 文章目录 一、[题目链接三数之和](https://leetcode.cn/problems/3sum/submissions/515727749/)二、思路讲解三、代码演示 先赞后看养成习惯^ _ ^3 ❤️ ❤️ ❤️ 码字不易大家的支持就是我坚持下去的动力。点赞后不要忘了关注我哦 所属专栏:双指针算法 一、题目链接三数之和 二、思路讲解 方法一暴力求解 我们只需要遍历所有情况即可得到所有结果然后去重,由于时间复杂度比较高过不了需要优化O(3*n^3)) 方法二找规律 1.我们首先sort迭代器进行排序 2.排完序后我们开始遍历 3.如果从i0开始遍历lefti1,rightn-1 4.优化判断nums[i]是否大于0大于0后面的数都是单增的就直接break跳出 5.取nums[i]的相反数sum判断sum和a[left]a[right]的大小关系如果sum大于a[left]a[right]那么left,小于的话就right–,同时要满足leftright 6.为了去重判断下一个left和前一个left是否相同下一个right和前一个right是否相同相同就继续向前走i也是 7.时间复杂度On^3nlogn 三、代码演示
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint arr;sort(nums.begin(),nums.end());int i 0,n nums.size();for(i0;in;){if(nums[i]0)break;int left i1,right n-1,target -nums[i];while(leftright){int sum nums[left]nums[right];if(sumtarget) right--;else if(sumtarget) left;else{arr.push_back({nums[i],nums[left],nums[right]});left,right--;while(leftrightnums[left]nums[left-1]) left;while(leftrightnums[right]nums[right1]) right--;}}i;while(innums[i]nums[i-1]) i;}return arr;}
};
