数据结构与算法：双指针

前言

双指针其实和滑动窗口差不多，但能使用的场景比滑动窗口更广功能更强。滑动窗口的内容在我上一篇文章数据结构与算法：滑动窗口。

一、原理

双指针的关键还是分析题目单调性，从而保证指针可以单方向滑动。

二、题目

1.按奇偶排序数组 II

class Solution {
public:vector<int> sortArrayByParityII(vector<int>& nums) {int n=nums.size();for(int even=0,odd=1,i=n-1;even<n&&odd<n;){if(nums[i]%2==0){swap(even,i,nums);even+=2;}else {swap(odd,i,nums);odd+=2;}}   return nums;}void swap(int a,int b,vector<int>&nums){int t=nums[a];nums[a]=nums[b];nums[b]=t;}
};

 这个题还是比较简单的，设置两个指针分别指向奇数位置和偶数位置的思路很好想，重点是每次去看的位置。这里设置为只盯着数组最后一个数看，然后把这个数往前发送，就可以避免每次讨论指针该不该滑动的问题。

2.寻找重复数

class Solution {
public:int findDuplicate(vector<int>& nums) {//寻找链表入环节点int slow=nums[0];int fast=nums[nums[0]];while(slow!=fast){slow=nums[slow];fast=nums[nums[fast]];}fast=0;//头节点为0！nums[0]已经跳过一次while(slow!=fast){slow=nums[slow];fast=nums[fast];}return slow;}
};

 这个题的思路就比较抽象了，首先考虑将数组的值看作链表的next指针，这样对用例画出链表的图后，会发现构成一个有环链表，所以考虑使用寻找有环链表的入环节点的快慢指针。

具体内容在我数据结构与算法：链表相关题目的文章中。

3.救生艇

class Solution {
public:int numRescueBoats(vector<int>& people, int limit) {//先排序sort(people.begin(),people.end());int n=people.size();int l=0,r=n-1;int ans=0;while(l<=r){int sum=l==r?people[l]:people[l]+people[r];if(sum>limit){r--;}else{l++;r--;}ans++;}return ans;}
};

 这个题的分析感觉有点像贪心，因为只要体重超了就得多用一艘船，所以当两个人体重超了的时候，肯定优先给大体重的人分船，而小体重的人可能还能跟别人拼船。

所以考虑先将数组排序，之后在头尾设置两个指针，若超了，就只给最右侧大体重的人分船。注意临界情况，当只剩一个人时，需要多给一艘船。

4.盛最多水的容器

class Solution {
public:int maxArea(vector<int>& height) {int n=height.size();int l=0,r=n-1;int ans=0;while(l<r){ans=max(ans,min(height[l],height[r])*(r-l));if(height[l]<height[r]){l++;}else{r--;}}return ans;}
};

 这个题就体现出分析题目单调性的重要了。分析题目，可以发现，水的体积和高度、长度之间都存在单调性关系，所以，同样在头尾设置两个指针，控制长度变量的单调性，接着根据两指针位置的高度，每次滑动较小高度的指针，即可保证高度变量的单调性。

具体分析就是，每次l到r范围上，水体积的最大值必然是此时l到r的距离乘以l和r的最小值。当l不动时，即水的高度由最小值l决定，由于r只能向左滑，所以距离必然减小。而无论r的高度增加与否，因为l不动，所以即使r的高度增大，水的高度仍然是两者最小值l。同理当r不动时情况类似。

5.供暖器

class Solution {
public:int findRadius(vector<int>& houses, vector<int>& heaters) {//先排序sort(houses.begin(),houses.end());sort(heaters.begin(),heaters.end());int ans=0;for(int i=0,j=0;i<houses.size();i++){while(!best(i,j,houses,heaters)){j++;}ans=max(ans,abs(heaters[j]-houses[i]));}return ans;}bool best(int i,int j,vector<int>&houses,vector<int>&heaters){return j==heaters.size()-1||abs(heaters[j]-houses[i])<abs(heaters[j+1]-houses[i]);}
};

 这个题的重点还是单调性，从常理出发，一般都会想到先对两个数组排序。

之后就是单调性分析，因为要求加热半径最小，而两数组又有序，所以最小的加热半径就是每个房屋到最近的加热器距离的最大值。（我想不出更好的解释方法了，感觉靠的就是直觉和常识）

所以在两数组上分别设置一个指针，若该房屋到下一个加热器的距离更小，就跳到下一个加热器。注意这里若距离相等也要让j往下跳，不然j就会一直被锁死在这个地方。

6.接雨水

class Solution {
public:int trap(vector<int>& height) {return solve2(height);}int solve1(vector<int>&height){int n=height.size();vector<int>leftMax(n,0);leftMax[0]=height[0];vector<int>rightMax(n,0);rightMax[n-1]=height[n-1];for(int i=1;i<n;i++){leftMax[i]=height[i]>leftMax[i-1]?height[i]:leftMax[i-1];}for(int i=n-2;i>=0;i--){rightMax[i]=height[i]>rightMax[i+1]?height[i]:rightMax[i+1];}int ans=0;for(int i=0;i<n;i++){   ans+=max(0,min(leftMax[i],rightMax[i])-height[i]);}return ans;}//双指针优化int solve2(vector<int>&height){int n=height.size();int leftMax=height[0];int rightMax=height[n-1];int l=1,r=n-2;int ans=0;while(l<=r){if(leftMax>=rightMax){ans+=max(0,rightMax-height[r]);rightMax=max(rightMax,height[r--]);}else{ans+=max(0,leftMax-height[l]);leftMax=max(leftMax,height[l++]);}}return ans;}
};

 这个题也是很经典的一道题了，感觉双指针的思路反而不太好想。

首先第一个思路就是纯暴力，因为每个位置的水量只取决于左右两侧最大值，所以先构建出左右两侧最大值的数组，之后逐一比较即可。

第二个方法就是双指针优化的解。和第四个题盛最多水的容器的单调性类似，只需要在头尾设置两个指针，然后再维护左右两侧最大值，最后每次结算最大值小的那侧即可。

7.缺失的第一个正数

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int l=0;int r=nums.size();while(l<r){if(nums[l]==l+1){l++;}else if(nums[l]<=l||nums[l]>r||nums[nums[l]-1]==nums[l]){swap(l,--r,nums);}else{swap(l,nums[l]-1,nums);}}return l+1;}void swap(int a,int b,vector<int>&nums){int t=nums[a];nums[a]=nums[b];nums[b]=t;}
};

 这个题就有点抽象了，这个思路根本不知道怎么想出来的。

首先分析题目，可以发现，数组长度为n，所以缺失的最小正整数一定在1~n+1之间。所以考虑在头尾设置两个指针，l表示左侧的数都已经处在该在的位置，即不缺失，r表示若在没有缺失的理想情况下，数字范围的右边界，最后。

之后遍历数组，将大小为l的数放到l+1位置。其中，若正好相等，则让l往下滑；若l位置的数小于等于l，则说明是垃圾值；若大于r，说明不符合理想情况，也是垃圾值；若nums[l]-1位置上的数等于l位置上的数，说明遇到重复的数且重复的数已经在该在的位置，也是垃圾值。对于垃圾值，只需要将其扔到r-1位置即可。若都不成立，说明该数符合理想情况，就把他发送到该在的位置。

总结

可以看出，因为指针不会回退，所以双指针确实可以极大程度上优化代码，基本上时间复杂度都非常良好，就是这个题目的单调性很不好想。

END