数据结构和算法笔记3：双指针法（快慢指针）

双指针法（快慢指针法）在数组、字符串和链表的操作中是非常常见的，这里结合力扣上的题进行可一下梳理，主要的思路是我们要明确快指针指的是什么，慢指针指的是什么。

1. 移除元素类问题

27. 移除元素

要我们移除目标元素，返回移动后元素的新长度。

• 快指针：原数组的索引，这里是fast
• 慢指针：移除后数组的索引，这里是slow

我们循环时一定是快指针遍历整个数组，然后慢指针根据条件移动，如果发现快指针不等于指定的目标元素val：nums[fast] != val，我们对当前的nums[slow]赋值为nums[fast]，让后slow自增。

class Solution {
public:int removeElement(vector<int>& nums, int val) {int slow = 0;for (int fast = 0; fast < nums.size(); ++fast){if (nums[fast] != val)nums[slow++] = nums[fast];}return slow;}
};

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

要我们移除数组重复的元素，返回移动后元素的新长度。

• 快指针：原数组的索引，这里是fast
• 慢指针：移除后数组的索引，这里是slow

为了看是否有重复项我们一定是比较nums[fast]和nums[fast - 1]看是否相等，如果不相等，说明不重复，我们可以把当前的nums[fast]赋值给nums[slow]，并且slow往前移动一位，为了fast-1不越界，fast的遍历应该从1开始，也是遍历整个数组，既然从1开始，slow的初始值也应该是1，因为第一个元素我们认为不需要删除。

class Solution {
public:int removeDuplicates(vector<int>& nums) {int slow = 1;for (int fast = 1; fast < nums.size(); ++fast){if (nums[fast] != nums[fast - 1])nums[slow++] = nums[fast];}return slow;}
};

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

要我们移除数组重复的元素，返回移动后元素的新长度，每个元素最多有2个。

• 快指针：原数组的索引，这里是fast
• 慢指针：移除后数组的索引，这里是slow

朴素的思路是判断nums[fast]前后元素是否和nums[fast]一样。

class Solution {
public:int removeDuplicates(vector<int>& nums) {int slow = 1;for (int fast = 1; fast < nums.size(); ++fast){if (fast < nums.size() - 1){if (!(nums[fast] == nums[fast - 1] && nums[fast] == nums[fast + 1]))nums[slow++] = nums[fast];}else{nums[slow++] = nums[fast];//最后一个元素不管重不重复都放进来，因为至少要2个}}return slow;}
};

其实可以不拘泥于26题的写法：

class Solution {
public:int removeDuplicates(vector<int>& nums) {int n = nums.size();if (n <= 2)return n;int slow = 2;for (int fast = 2; fast < n; ++fast){if (nums[slow - 2] != nums[fast])nums[slow++] = nums[fast];}return slow;}
};

移除保留最多k个元素的通用写法：

class Solution {
public:int removeDuplicates(vector<int>& nums) {int n = k;if (nums.size() <= k)return n;int slow = k;for (int fast = k; fast < nums.size(); ++fast){if (nums[slow - k] != nums[fast])nums[slow++] = nums[fast];}return slow;}
};

283.移动零

要我们把零全部移动到最后，一种直观的思路是使用移除元素的方法，把零移除完，然后从这时的slow开始把数组后面的值都赋值为0：

• 快指针：原数组的索引，这里是fast
• 慢指针：移除后数组的索引，这里是slow

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

但我们要移动0，其实也可以直接进行位置的调换，每当发现一个nums[fast]的值不为0，我们就调换当前nums[slow]和nums[fast]的值(而不是把nums[fast]直接幅值给nums[slow])，然后slow自增：

class Solution {
public:void moveZeroes(vector<int>& nums) {int slow = 0;for (int fast = 0; fast < nums.size(); ++fast){if (nums[fast] != 0){swap(nums[slow++], nums[fast]);}}}
};

844. 比较含退格的字符串

要我们比较两个字符串（包含退格后）是否等，两个字符串都定义快指针和慢指针

• 快指针：原数组的索引，这里是sfast和tfast
• 慢指针：退格后数组的索引，这里是sslow和tslow

对两个字符串都进行快慢指针，退格的时候slow指针自减，因为我们要用到nums[slow++]，slow至少为0，所以在slow为0的时候我们规定不自减。

class Solution {
public:bool backspaceCompare(string s, string t) {int sfast = 0;int sslow = 0;int tfast = 0;int tslow = 0;for (; sfast < s.size(); ++sfast){if (s[sfast] != '#')s[sslow++] = s[sfast];else if (sslow != 0)sslow --;}for (; tfast < t.size(); ++tfast){if (t[tfast] != '#')t[tslow++] = t[tfast];else if (tslow != 0)tslow --;}if (tslow != sslow)return false;else{for (int i = 0; i < tslow; ++i){if (t[i] != s[i])return false;}}return true;}
};

增加元素类题目

1089. 复写零

要我们对输入的数组就地进行上述修改，将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

• 快指针：原数组的索引，这里是i
• 慢指针：复写零新数组的索引，这里是j

按照题目要求如果原数组的元素arr[i]碰到0，新数组的索引arr[j]要额外走一步，直到新数组索引越界走出整个循环.

这时候要注意的是原数组多走了一步，我们需要对原数组和新数组进行一步回退。

然后往回赋值（逆序遍历），循环继续进行的条件是原数组的索引i大于等于0，如果新数组索引j没有越界，就把arr[i]的值赋值给arr[j]，如果arr[i]碰到0，我们要判断当前索引j前面能不能再赋值（有没有越界），如果可以就把j自减，并且arr[j]赋值为0，接着索引i和j继续自减回退，直到循环结束条件达到，数组也就成功复写了零：

class Solution {
public:void duplicateZeros(vector<int>& arr) {int len = arr.size(); int i = 0;int j = 0;while (j < len){if (arr[i] == 0)j++;i++;j++;}i--;j--;while (i >= 0){if (j < len)arr[j] = arr[i];if (arr[i] == 0 && j - 1 >= 0){j--;arr[j] = 0;}i--;j--;}}
};