初识算法 · 双指针(3)
目录
前言：
本文通过介绍和为S的两数之和，以及三数之和，对双指针算法进行深一步的了解，介绍该算法博主使用三部曲，第一步对题目进行分析，里面会夹杂着暴力解法的问题，第二步对于算法原理进行分析，第三步则是对算法进行编写，最后分析时间复杂度，可能会分析空间复杂度。
题目的链接为：
LCR 179. 查找总价格为目标值的两个商品 - 力扣（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: vector<int> twoSum(vector<int>& 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: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> 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; } };三个去重，一个排序，三个判断，最后返回即可。
感谢阅读！
