模型总结：前后指针法

零、前言

作者为了找工作和实习开启了自己的算法之旅，并将刷到的各种题型总结成模型分享给大家。

一、最基本的前后指针法

本文将持续更新。

27. 移除元素

1.使用场景

前后指针法，与其说是一个题型，不如说是一种思想：

在一个数组中筛选符合条件的元素，并放在原数组中。

2.思路

定义一个快指针和一个慢指针。
快指针依次遍历数组，在for循环内递增。
慢指针在快指针筛选出来符合条件的元素时，nums[slow]=nums[fast]，slow++
总结来说就是slow筛选下标，而fast来筛选元素。

3.实现

class Solution {
public:
    int removeElement(vector& nums, int val) {
        int slowstr=0;//定义慢指针为数组下标
        int faststr=0;//定义快指针指向所需的值
        for(faststr=0;faststr<nums.size();faststr++)
        {
            if(nums[faststr]!=val)
            {
                nums[slowstr]=nums[faststr];
                slowstr++;
            }
        }
        return slowstr;
    }
};

在移除元素中就体现为移除满足条件的元素。然后再放在原数组中。

二、变式一：多元素去重

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

1.思路

多元素去重，本质上就是筛选出数组中多个相等的元素。题目要求使用原数组，因此可以考虑前后指针法，只需要将slow++放在nums[slow]=nums[fast]之后即可。

2.实现

class Solution {
public:
    void moveZeroes(vector& nums) {
        int faststr=0;
        int slowstr=0;
        for(faststr=0;faststr<nums.size();faststr++)
        {
            if(nums[faststr]!=0)
            {
                nums[slowstr]=nums[faststr];
                slowstr++;
            }
        }
        for(int i=slowstr;i<faststr;i++)
        {
            nums[i]=0;
        }
    }
};

本题给我们的启示为，当在相同数组中进行筛选的时候可以优先考虑前后指针法，这里给了条件是升序数组。所以说还需要有一定的条件，根据该条件来调整代码即可。

三、变式二：筛选元素具有某种属性

844. 比较含退格的字符串

1.思路

首先依然满足条件，筛选出来的元素存放在原数组中，而具有某种属性最终会体现在slow指针如何处理上。fast指针继续正常遍历即可。

在这里每当发生退格的时候，slow--，并且当--为小于0的数时，将其置为0。

2.实现

class Solution {
public:
    string StrSolution(string str)
    {
        int faststr=0;
        int slowstr=0;
        for(faststr=0;faststr<str.size();faststr++)
        {
            if(slowstr<0)
            {
                slowstr=0;
            }
            if(str[faststr]!='#')
            {
                str[slowstr]=str[faststr];
                slowstr++;
            }
            else
            {
                slowstr--;
            }
        }
        if(slowstr<0)
        {
            slowstr=0;
        }
        str[slowstr]='\0';
        str = str.substr(0, slowstr);
        return str;
    }
    bool backspaceCompare(string s, string t) {
        string s1=StrSolution(s);
        string s2=StrSolution(t);

        if(s1==s2)
        {
            return true;
        }
        else 
        {
            return false;
        }
    }
};