-
算法模型总结：前后指针法
一、最基本的前后指针法
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 - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
在移除元素中就体现为移除满足条件的元素。然后再放在原数组中。
二、变式一：多元素去重
1.思路
多元素去重，本质上就是筛选出数组中多个相等的元素。题目要求使用原数组，因此可以考虑前后指针法，只需要将slow++放在nums[slow]=nums[fast]之后即可。
2.实现
class Solution { public: void moveZeroes(vector& nums) { int faststr=0; int slowstr=0; for(faststr=0;faststr - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
本题给我们的启示为，当在相同数组中进行筛选的时候可以优先考虑前后指针法，这里给了条件是升序数组。所以说还需要有一定的条件，根据该条件来调整代码即可。
三、变式二：筛选元素具有某种属性
1.思路
首先依然满足条件，筛选出来的元素存放在原数组中，而具有某种属性最终会体现在slow指针如何处理上。fast指针继续正常遍历即可。
在这里每当发生退格的时候，slow–，并且当–为小于0的数时，将其置为0。
2.实现
class Solution { public: string StrSolution(string str) { int faststr=0; int slowstr=0; for(faststr=0;faststr
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
3.发现的问题
其中如果不使用字符串切割，string类不会因为看到’\0’而结束。但是如果在构造的时候有’\0’那么可以结束。因此还需要进行字符串切割。
三、变式四：三数之和
- 三数之和
这道题需要理清逻辑就很简单：
使用哈希难以进行去重的处理，因此使用三指针法，在使用之前需要进行排序，让i表示一个指针,left表示一个指针指向i+1，right指向最后一个元素。
去重的逻辑是(nums[i]==nums[i-1])则continue。left和right的去重逻辑一样：
class Solution {
public:
vector> threeSum(vector& nums) {
vector> result;
sort(nums.begin(),nums.end());
for(int i=0;i0&&nums[i]==nums[i-1])
{
continue;
}
int left=i+1;
int right=nums.size()-1;
while(left0)
{
right--;
}
else
{
left++;
}
}
}
return result;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
四、总结
前后指针法不是一个固定的题型，重要点在于识别。
- 当发现存放的元素放在原数组中的时候，就可以考虑使用前后指针法了。往往还伴随着一些条件。
- 筛选的元素可以带有一些属性，使用slow指针来体现。
本文将持续进行更新。