双指针法(快慢指针法)在数组、字符串和链表的操作中是非常常见的,这里结合力扣上的题进行可一下梳理,主要的思路是我们要明确快指针指的是什么,慢指针指的是什么。
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;}
};
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]);}}}
};
增加元素类题目
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--;}}
};