双指针例题

移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
暴力解法：双层for循环
双指针法：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

844. 比较含退格的字符串
一个字符是否被删除取决于其后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。
我们定义skip来表示当前待删除的字符的数量，每当我们遍历一个字符：

• 若该字符为退格符，则我们需要多删除一个普通字符，我们让skip 加 1；
• 若该字符为普通字符：

•  若 skip 为 0，则说明当前字符不需要删去；
  1

•  若 skip 不为 0，则说明当前字符需要删去，我们让 skip 减 1。
  1

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int sRight = s.size()-1;
        int tRight = t.size()-1;
        int skipS = 0;
        int skipT = 0;
        while(sRight >= 0 || tRight >=0){
            while(sRight >= 0){
                if(s[sRight] == '#'){
                    sRight--,skipS++;
                }else if(skipS > 0){
                    sRight--,skipS--;
                }else{
                    break;
                }
            }
            while(tRight >= 0){
                if(t[tRight] == '#'){
                    tRight--,skipT++;
                }else if(skipT > 0){
                    tRight--,skipT--;
                }else{
                    break;
                }
            }
            if(sRight >= 0 && tRight >= 0){
                if(s[sRight] != t[tRight]){
                    return false;
                }
            }else{
                if(sRight >= 0 || tRight >= 0){
                    return false;
                }
            }
            sRight--,tRight--;
        }
        return true;
    }
};
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

76. 最小覆盖子串
利用滑动窗口的思想，有一个左指针，一个右指针，右指针用于延伸现有窗口，左指针用于收缩现有窗口，在任意时刻都只有一个指针运动，我们通过移动右指针不断扩充滑动窗口，直到窗口包含t中所有的字符时停止开始检查（这里检查用到两个hash表，分别是用于s和t，因为要考虑字符的数量，所以用key表示字符，value表示出现的数量），如果左窗口可以收缩，就移动左指针缩小到最小窗口