wordpress适合做什么网站,现在最流行的网站开发工具,代做机械毕业设计网站,怎么查看网页源代码目录
前言#xff1a;
和为s的两数之和
题目解析#xff1a;
编辑
算法原理#xff1a;
算法编写#xff1a;
三数之和
题目解析
算法原理
算法编写 前言#xff1a;
本文通过介绍和为S的两数之和#xff0c;以及三数之和#xff0c;对双指针算法进行深一步…目录
前言
和为s的两数之和
题目解析
编辑
算法原理
算法编写
三数之和
题目解析
算法原理
算法编写 前言
本文通过介绍和为S的两数之和以及三数之和对双指针算法进行深一步的了解介绍该算法博主使用三部曲第一步对题目进行分析里面会夹杂着暴力解法的问题第二步对于算法原理进行分析第三步则是对算法进行编写最后分析时间复杂度可能会分析空间复杂度。
题目的链接为
LCR 179. 查找总价格为目标值的两个商品 - 力扣LeetCode
15. 三数之和 - 力扣LeetCode
那么话不多说进入正题吧 和为s的两数之和
题目解析 该题目的要求是找到两个数这两个数相加的和是等于target的。题中也有个很重要的条件按照升序记录于数组中这个升序是十分关键的。我们直接探讨暴力解法即将所有的两数之和举例出来第一次相等就返回即可如果运气差点就需要遍历完整个数组两次即两个for循环此时的时间复杂度为O(N^2)这是暴力解法是比较容易想出来的
for (int i 0; i price.size();i)
{for (int j 0;j price.size();j){//判断是否满足条件}
}
当然了如果使用暴力解法那么我们对题目的升序就没有任何使用了就很吃亏所以现在进入算法原理。
算法原理
使用双指针算法对于题目中的升序一定要利用好我们知道 target num1 num2 那么既然是升序的如果我们让两个指针一个从开始走一个从末尾走也就是最大的和最小的走判断结果大于了target右指针往左边走反之亦然这时候其实已经做完题目了。
对于循环来说只有一个循环如果没有找到返回的是个空就可以。
算法编写
class Solution
{
public:vectorint twoSum(vectorint price, int target) {int right price.size() - 1, left 0;while(left right){if(price[left] price[right] target)return {price[left],price[right]};else if(price[left] price[right] target) left;else if(price[left] price[right] target) right--;}return { };}
};
结束条件自然是左小于右因为返回的是vector都没有找到的话返回空即可时间复杂度是O(N),没有新开空间所以空间复杂度为O(1)。 三数之和
题目解析 由题目可得找三个数其中这三个数相加等于0我们不妨将题目理解为找一个数该数 另外两数之和是不是就感觉容易多了不过是上文和为s的变种而已我们只是需要将S变化一下即可。
以上是题目的最基本的要求那么还有一个要求是不允许出现重复的这是和本文第一道题不同的要求这点代表了我们要去重即可。
那么同样的我们思考如何暴力解法
暴力解法无非是将所有的三元组列出来判断和是否为零满足条件我们可以将它丢进set用set本身的性质进行去重即可。
但是暴力解法的时间复杂度可就高了三个数都要单独列出也就是需要三个循环时间复杂度为O(N^3)往往是通过不了的。
所以我们进入到算法原理方面。 算法原理
我们同样的使用双指针算法因为是双指针不是三指针所以需要我们固定一个数用来充当target有了第一个题目的经验我们不妨排序一下保证数组有序的同时有利于我们控制指针变量排序之后对于我们去重的操作也会容易很多。
排序之后固定好target然后进入到第二个循环通过双指针算法找两个数使该三个数相加等于0即可。
那么指针移动分为两种情况如果前面两个数相加target代表right大了需要right--反之亦然这是移动的情况。满足条件的话添加进去就可以了。
那么最重要的点来了我们如何进行去重操作呢
判断的是nums[left] nums[left 1]是否相等即可如果相等了left就right同理但是去重的不只有这两个数还有一个数也需要去重就是nums[i]如果i不去重肯定是很导致很多重复的元素毕竟都是会从头开始找的。
去重i的时候需要控制i的移动因为去重操作本身就会控制指针移动。 算法编写
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ans;sort(nums.begin(),nums.end()); for(int i nums.size() - 1;i 1 nums[i] 0;){int target nums[i];int left 0,right i - 1;while(left right){if(nums[left] nums[right] (-target)) right--;else if(nums[left] nums[right] (-target)) left;else{ans.push_back({nums[left],nums[right--],nums[i]});while(left right nums[left] nums[left - 1]) left;while(left right nums[right] nums[right 1]) right--;}}i--;while(i nums.size() nums[i] nums[i 1]) i--;}return ans;}
};
三个去重一个排序三个判断最后返回即可。 感谢阅读
