建设网站的时候,随州北京网站建设,杭州网站界面设计,微帮推广平台怎么加入三数之和
#xff08;1#xff09;排序双指针 算法思路#xff1a; 和之前的两数之和类似#xff0c;我们对暴力枚举进行了一些优化#xff0c;利用了排序双指针的思路#xff1a; 我们先排序#xff0c;然后固定⼀个数 a #xff0c;接着我们就可以在这个数后面的区间… 三数之和
1排序双指针 算法思路 和之前的两数之和类似我们对暴力枚举进行了一些优化利用了排序双指针的思路 我们先排序然后固定⼀个数 a 接着我们就可以在这个数后面的区间内使用之前两数之和使用的算法快速找到两个数之和和固定的a等于target即可。 但是要注意为了避免其中有重复的解: 我们需要在找到⼀个结果之后 left 和 right 指针要跳过重复的元素同时在使用完一次双指针算法之后固定的 a 也要跳过重复的元素。 算法实现过程 给定一个包含n个整数的数组nums函数返回所有不重复的三元组[a, b, c]使得a b c 0。函数首先对数组进行排序然后使用双指针的方法来遍历数组。外层循环通过变量i遍历数组内层循环通过变量left和right来找到满足条件的三元组。 如果三数之和小于0则将left右移一位如果大于0则将right左移一位如果等于0则将三个数加入结果数组ret并继续移动left和right直到找到不重复的三元组。最后返回结果数组ret。 class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());//排序vectorvectorint ret;//定义一个二维数组int nnums.size();for(int i0;in;){int lefti1;int rightn-1;if(nums[i]0) break;//如果最小值大于0那结果一定大于0while(leftright){int sumnums[i]nums[left]nums[right];if(sum0) left;//三数之和小于0leftelse if(sum0) right--;//三数之和大于0right--else {ret.push_back({nums[i],nums[left],nums[right]});left;//找到了一组解后left和right都要改变right--;//避免重复的解while(leftrightnums[left]nums[left-1]) left;while(leftrightnums[right]nums[right1]) right--;}//跳过相同的值也是为了避免重复的解}i;//i也要跳过相同的值而且i不可以越界所以要inwhile(innums[i]nums[i-1]) i;}return ret;}
};时间复杂度O(n2) 四数之和
1排序双指针 实现方式和三数之和类似固定两个数即可。
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint ret;//定义一个二维数组sort(nums.begin(),nums.end());//排序int nnums.size();for(int i0;in;)//固定第一个数{for(int ji1;jn;)//固定第二个数{int leftj1;int rightn-1;//后面的测试用例比较大用long longlong long aim(long long)target-nums[i]-nums[j];while(leftright){int sumnums[left]nums[right];if(sumaim) right--;//如果四数之和大于目标值right--else if(sumaim) left;//如果四数之和小于目标值,leftelse {ret.push_back({nums[i],nums[j],nums[left],nums[right]});left;//left,right--避免有重复的情况right--;//跳过相同的数while(leftrightnums[left]nums[left-1]) left;while(leftrightnums[right]nums[right1]) right--;}}j;//跳过和第二个数相同的数while(jnnums[j]nums[j-1]) j;}i;//跳过和第一个数相同的数while(innums[i]nums[i-1]) i;}return ret;}
};时间复杂度O(N3)
