目录
前言
本文通过介绍和为 S 的两数之和，以及三数之和，对双指针算法进行深一步的了解。
和为 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;
}
};
三个去重，一个排序，三个判断，最后返回即可。
