算法知识-双指针
一.双指针
设置两个指针的技巧，说法很宽泛。
(1)有时候所谓双指针技巧，就是单纯代码过程用双指针的形式表达出来而已，没有单调性(贪心)方面的考虑(例题1，例题2）
(2)有时候双指针技巧包含单调性(贪心)方面的考虑，牵扯到可能性的取舍，对于分析能力的要求会变高，其实是先有思考和优化，然后代码变成了双指针的形式
(3)所以，双指针名词并不重要，分析题目单调性(贪心)方面的特征，这个能力才重要
常见双指针类型：
同向双指针
快慢双指针
从两头往中间的双指针
其他
二.例题
922. 按奇偶排序数组 II - 力扣（LeetCode）
我们安排两个指针，一个是奇数指针从下标1出发，一个是偶数指针从下标0出发，我们盯着数组最后一个位置，不断看最后一个位置是奇数还是偶数，如果是奇数就和奇数下标交换一下，之后odd+=2,如果是偶数就和偶数下标交换一下，之后even+=2，循环结束条件是even或者odd越界，说明有奇数/偶数位置已经安排妥当，那么整体就已经安排妥当。
总结：以数组最后一位去发货，不断让奇数位和偶数位去成长，谁先成长越界就说明谁已经安排妥当
class Solution { public: vector<int> sortArrayByParityII(vector<int>& nums) { int n=nums.size(); for(int even=0,odd=1;even<n&&odd<n;){ if(nums[n-1]&1){ swap(nums[n-1],nums[odd]); odd+=2; }else{ swap(nums[n-1],nums[even]); even+=2; } } return nums; } };287. 寻找重复数 - 力扣（LeetCode）
我们可以把数组想象成链表的形式，那么i指向nums[i],如果有重复的数字，那么链表一定成环，可以使用快慢指针
补充：快慢指针
(1)快指针一次跳两步，慢指针一次跳一步
(2)快慢指针相遇
(3)快指针回到起点，慢指针留在原处，每人一次跳一步，直到相遇，就是环的入口
class Solution { public: int findDuplicate(vector<int>& nums) { int n=nums.size(); int slow=nums[0]; int fast=nums[nums[0]]; while(slow!=fast){ slow=nums[slow]; fast=nums[nums[fast]]; } fast=0; while(fast!=slow){ fast=nums[fast]; slow=nums[slow]; } return slow; } };42. 接雨水 - 力扣（LeetCode）
首先我们分析题目，对于任意一个位置i它所能承接的雨水，由于木桶的短板效应，所以水的高度，加上自身高度不能超过，左右两侧最大值的最小值，即能承接min(lMax,rMax)-a[i]，但是由于i位置可能比左右两侧最大值都高，会计算出负数，所以i位置能承接的雨水应该是max(min(lMax,rMax)-a[i],0)，之后我们通过前缀最大值分别记录每个位置左侧和右侧的最大值
class Solution { public: int trap(vector<int> &height) { int n = height.size(); vector<int> lMax(n); vector<int> rMax(n); lMax[0] = height[0]; for (int i = 1; i < n; i++) { lMax[i] = max(lMax[i-1], height[i]); } rMax[n - 1] = height[n - 1]; for (int i = n -2; i >= 1; i--) { rMax[i] = max(rMax[i+1], height[i]); } int ans = 0; for (int i = 1; i < n-1; i++) { ans += max((min(lMax[i], rMax[i]) - height[i]), 0); } return ans; } };双指针优化
我们可以设置两个指针，l，r从1和n-2出发，之后维护一个lMax，和一个rMax，如果lMax<=rMax,l左侧为lMax,而l右侧应该>=rMax，那么l位置的短板一定是lMax，否则lMax>rMax,r右侧为真实的rMax,而r左侧应该>=lMax,所以r位置的短板应该是rMax，左指针l非严格单调递增（仅右移、不回退），右指针r非严格单调递减（仅左移、不回退）
int trap(vector<int> &height) { int n = height.size(); int l=1,r=n-2,lMax=height[0],rMax=height[n-1]; int ans=0; while(l<=r){ if(lMax<=rMax){ ans+=max(lMax-height[l],0); lMax=max(lMax,height[l++]); }else{ ans+=max(rMax-height[r],0); rMax=max(rMax,height[r--]); } } return ans; }881. 救生艇 - 力扣（LeetCode）
我们首先对原数组排序，之后设置两个指针，l,r分别在开头和结尾
(1)a[l]+a[r]<=limit
l和r一船，因为对于l来说已经是最值的选择了
l++，r--
(2)a[l]+a[r]>limit
那么r自己一船，因为l右侧都是比l大的，不会有能和r一船的了
r--
class Solution { public: int numRescueBoats(vector<int>& people, int limit) { sort(people.begin(),people.end()); int l=0,r=people.size()-1; int ans=0; int sum=0; while(l<=r){ sum=l==r?people[l]:people[l]+people[r]; if(sum<=limit){ l++; r--; }else{ r--; } ans++; } return ans; } };11. 盛最多水的容器 - 力扣（LeetCode）
题目分析：
设置两个指针l,r分别从开头和结尾出发，如果h[l]<=h[r]，以h[l]为开头的最好的情况就是现在，当前边长最长，并且以h[l]为开头一定要<=h[l]。所以更新一下答案，l++
反之，如果h[l]>h[r],以h[r]作为结尾最好情况就是现在，以h[r]作为结尾一定要<=h[r]，并且现在边长最大
所以就是谁小就以谁作边长，并且移动谁
class Solution { public: int maxArea(vector<int>& height) { int res = 0; int l = 0; int r = height.size() - 1; while (l < r) { int area = (r - l) * min(height[l], height[r]); res = max(res, area); if (height[l] <= height[r]) { l++; } else { r--; } } return res; } };475. 供暖器 - 力扣（LeetCode）
题目分析：本道题目比较简单，先对两个数组进行排序，就是一个指针l1从房屋出发，一个指针l2从供暖器出发，之后我们循环比较l1房屋到l2+1供暖器的距离是否小于等于l1到l2的距离呢，是的话说明l2+1更好,l2++，之后当l2移动到最后说明已经没有更大的供暖期进行选择了，我们只能选择l2了。
注意：如果l2距房屋距离与l1距房屋距离相等l2一定要移动，因为供暖器数组可能存在两个相等的值，如果不移动将会永远无法移动l2导致后续计算错误
class Solution { public: int findRadius(vector<int>& houses, vector<int>& heaters) { sort(houses.begin(),houses.end()); sort(heaters.begin(),heaters.end()); int n=houses.size(),m=heaters.size(); int l1=0,l2=0; int diff1=0,diff2=0; int ans=0; for(int l1=0;l1<n;l1++){ if(l2==m-1){ ans=max(ans,abs(houses[l1]-heaters[l2])); continue; } while(l2<m-1&&abs(houses[l1]-heaters[l2+1]) <=abs(houses[l1]-heaters[l2])){ l2++; } ans=max(ans,abs(houses[l1]-heaters[l2])); } return ans; } };41. 缺失的第一个正数 - 力扣（LeetCode）
该题目比较难想。
题目分析：
如果正常的话就应该是a[l]=l+1,那么一开始我们假设每一个位置都是这样的那么我们能收集1~n都会存在，所以我们一开始有一个左指针l从0出发，代表l左侧是放好的，r从下标n出发代表垃圾区域，有一下几种情况
(1)a[l]==l+1，正常放置l++
(2)垃圾数据:
a[l]>r，只能收集1~r,大于r一定是垃圾
a[l]<=l,小于等于l在l左侧已经收集好了，垃圾
a[a[l]-1]==a[l]，如果a[l]在l+1到r之间，需要把a[l]放到对应的位置上，但是发现该位置已经有相同的数字了，垃圾
把a[l]交换到垃圾区，swap(nums[l],nums[--r])
(3)不是垃圾，也不是该位置的数字，需要给他交换到它的位置上去
swap(nums[l],nums[nums[l]-1])
class Solution { public: int firstMissingPositive(vector<int>& nums) { int l=0,r=nums.size(); while(l<r){ if(nums[l]==l+1){ l++; }else if(nums[l]>r||nums[l]<=l||nums[nums[l]-1]==nums[l]){ swap(nums[l],nums[--r]); }else{ swap(nums[l],nums[nums[l]-1]); } } return l+1; } };