双指针总结

双指针简介

　　双指针法是处理线性结构问题众多巧妙思路中的一种。大多数时候，使用双指针的方法可以有效地改善代码的性能。顾名思义，双指针法需要使用两个指针来处理线性结构，一般来说，两个指针的作用分别如下：一个指针负责遍历线性结构，另一个指针一般用于指向下一个有效的空位，用于放置最终结果。
　　双指针的思路不仅限于两个指针，根据需要可以根据情况分出更多指针，以分类存放结果。总体来说，双指针的思路可以认为是一边遍历给定的元素，一边进行分类处理。两个指针的情况无非就是合法的元素被存放，不合法的元素被抛弃而已。由此，可以对此方法进行扩展，比如三指针、四指针等等。

双指针伪代码

int mysolution(){
    //其中一个为遍历指针i，一个为用于指示存放位置的指针index
    int i,index;
    for(使用i遍历所有的元素){
        if(当前元素满足要求){
            放入index所指向的存放位置;
        }
    }
    return value;
}

双指针使用示例

26.删除有序数组中的重复项

　　使用一个指针i遍历整个数组，使用index指向存放的位置，覆盖存放那些不重复的数字。因为给出的数组是有序的，所以第一个或者与前一个数字不相同（新数字）的数字为不重复数字，需要存放。这样处理下来，最后index刚好就是不重复数字的个数。
　　解题代码如下：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int index=0,size=nums.size();   //index始终指向一个空位置
        for(int i=0;i<size;i++)         //如果是第一个数字，或者出现了不重复的数字，则追加在数组中
            if(i==0||nums[i]!=nums[index-1]) nums[index++]=nums[i]; 
        return index;
    }
};

977.有序数组的平方

　　此题可以认为是双指针的扩展，因为需要两个指针遍历给出的元素。此题遍历过程中，得到的结果还需要进行排序，实现过程有点类似于合并两个升序数组，只不过两个升序数组以一个数组的形式给出，需要自己做出划分而已。
　　解题代码如下：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left,right,size=nums.size(),index=0;    //三个指针，left向左侧遍历负数，right向右遍历0和正数
        const int INF=1e8+1;                        //定义一个无穷大标记
        vector<int> ans(size);                      //答案数组
        for(right=0;right<size;right++)             //首先找到非负数的起始位置
            if(nums[right]>=0) break;
        left=right-1;                               //确定负数起始位置
        while(left>=0||right<=size-1){              //只要有一个序列还没有遍历结束，就一直遍历
            int leftnum=left<0?INF:nums[left]*nums[left];   //确定两个序列中的数字，如果序列结束了，就用无穷大
            int rightnum=right>=size?INF:nums[right]*nums[right];
            if(leftnum<=right){                     //将两者中小的那一个加入答案序列
                ans[index++]=leftnum;
                left--;
            }
            else{
                ans[index++]=rightnum;
                right++;
            }
        }
        return ans;
    }
};