c++双指针思路

代码类型：双指针

解释：在代码中有两个指针，各自有指向数据的位置，通过移动两个指针，进行判断与修改实现一些功能。

通常用于数组操作，有两种方式，一种是前后两指针，相向而行，通常这种做法会改变元素顺序；另一种方式是快慢两指针，同向而行，操作过程一般不会改变元素相对顺序，又称为滑动窗口。

双指针（相向指针）的常用题型：排序数据（包含正数和负数）平方按排序、删除指定元素

双指针（滑动窗口）的常用题型：满足连续和的最小区间数目、包含子序列的最小窗口

滑动窗口的主要步骤：

1.初始化变量，快指针、慢指针（一般慢指针先初始化，循环里满足条件再变化，快指针在循环中每次自增一），有时候需要搭配哈希表，用于记录一些数据，一般是当前滑动窗口存在的数据种类及个数；

2.for循环，循环变量是快指针，所以每次循环快指针就会自增。

3.循环体中第一步是统计快指针指向的数据（存入哈希，累加等）；第二步是一个while循环或者if判断，这个循环用来尝试不断缩短滑动窗口，也就是慢指针增加，并更新当前的答案；

4.判断有没有满足条件的值，有的话输出。

典型题目分析

力扣  76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

代码

class Solution {
public:
    unordered_map s_con, t_con;
    //检查当前窗口的字符串和目标字符串是否匹配
    bool check(){
        for(auto i = t_con.begin(); i != t_con.end(); i++){
            char c = i->first;
            if(s_con[c] < t_con[c]){
                return false;
            } 
        }
        return true;
    }
    string minWindow(string s, string t) {
        if(t.size() > s.size()) return "";
        int n = t.size();
        //初始化统计t的字符出现的次数
        for(int i = 0; i < n; i++){
            t_con[t[i]]++;
        }
        //初始化滑动窗口
        n = s.size();
        //初始化慢指针以及最终答案值，最终答案先初始化为一个不可能出现的较大值
        int i = 0, ans_n = n + 1;
        string ans = s;
        //快指针在循环过程中每次自增1
        for(int j = 0; j < n; j++){
            s_con[s[j]]++;//滑动窗口向后扩大1，更新哈希
            while(check()){
                int temp = (j - i + 1);
                //更新结果值
                if(temp < ans_n){
                    ans_n = temp;
                    ans = s.substr(i, temp);
                }
                //尝试缩小滑动窗口，也就是将慢指针增加
                s_con[s[i]]--;
                i++;
            }
        }
        if(ans_n > n) return "";
        return ans;
    }
};