双指针算法介绍及使用（下）
在上一篇文章中我们已经对双指针有了一定了解，接下来我们通过题目来对双指针进行更好的理解。
1. leetcode 202. 快乐数
这道题使用的方法是快慢指针， 比如说一个数X，那么创建两个变量X1和X2，然后X1每次变化两次，X2变化一次，那么X1和X2肯定会相遇（假如说X不是快乐数，那么X1和X2会在一个变化范围内相遇，反之就是在1的位置相遇）。
PS：这道题在我看来不是传统意义上的快慢指针，在我看来跟多的是使用了其思想。
我们在代码里面使用了slow和fast两个指针来模拟相遇。
class Solution {
public:int happysum(int a){int count=0;while(a){int b=a%10;count+=b*b;a/=10;}return count;}bool isHappy(int n) {int slow=n;int fast=n;fast=happysum(fast);while(slow!=fast){slow=happysum(slow);fast=happysum(fast);fast=happysum(fast);}return fast==1;}
};2. leetcode 11. 盛最多水的容器
这道题的话暴力是肯定不行的，那么我们可以通过左右指针的方式 。简单来说就是最左和最右两边先进行一次计算，然后哪边短哪边移动，然后比较这几个值的大小就可以得到结果。
PS：我们也可以理解为计算横坐标在某个值时的最大值。
class Solution {
public:int maxArea(vector<int>& h) {int left=0;int n=h.size()-1;int right=n;int mymax=0;while(left<right){int count=min(h[left],h[right])*n;n--;if(h[left]>=h[right])right--;elseleft++;mymax=max(mymax,count);}return mymax;}
};3. leetcode 611. 有效三角形的个数
三角形三边需满足 “任意两边之和大于第三边”，但直接枚举所有三元组验证效率低（时间复杂度高）。所以需要利用排序 + 双指针优化。
简单来说，就是先拿一个最大的，然后在剩下的里面通过left++和right--来直接找到符合的区间，因为实现排好序了所以一旦找到直接right-left就可以了。
class Solution {
public:int triangleNumber(vector<int>& nums) {int count=0;sort(nums.begin(),nums.end());int n=nums.size()-1;for(int i=n;i>=2;--i){int left=0;int right=i-1;while(left!=right){if(nums[left]+nums[right]>nums[i]){count+=right-left;right--;}else{left++;}}}return count;}
};4. leetcode LCR 179. 查找总价格为目标值的两个商品
这道题也可以通过二分的方式来进行解决，在这里我们通过双指针的方式来进行解决。
简单来说就是先设一个left和一个right，然后通过t-p[left]的方式来得到一个值（即以p[left]为确定值的前提来查找有没有另一个值）。因为这个数组是升序的，所以说如果找不到就说明是p[left]太小了，所以left++即可。
class Solution {
public:vector<int> twoSum(vector<int>& p, int t) {int n=p.size();int left=0;vector<int> v;for(left=0;;++left){int right=n-1;while(left<right){if(t-p[left]>p[right])break;else if(t-p[left]<p[right]){right--;}else{v.push_back(p[left]);v.push_back(p[right]);return v;}}}}
};5. leetcode 15. 三数之和
这道题的话就和上面那到类似，唯一要注意的就是题目要求中说答案中不可以包含重复的三元组。
所以我们要先对其进行去重。三个数都有可能重复，所以三个数都要检查一下。
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> v;int n=nums.size();for(int i=0;i<=n-3;++i){if(i>0&&nums[i]==nums[i-1])continue;int left=i+1;int right=n-1;int t=nums[i];while(left<right){if(t+nums[left]+nums[right]>0){right--;}else if(t+nums[left]+nums[right]<0){left++;}else{v.push_back({nums[i],nums[left],nums[right]});while(left<right&&nums[left]==nums[left+1])left++;while(left<right&&nums[right]==nums[right-1])right--;right--;left++;}}}return v;}
};