双指针算法

tips:

1. 涉及到 重复 二字考虑用一个计数数组进行存储

左右指针

思路：设立两个指针 i 和 j ; 分别指向数组两端，在不同条件下，向内部移动某个指针，直到两个指针交互。

int i=0,j=n-1;
while(i<j){
    if(){
        v = ...;
        i++;
    }
    else{
        v = ...;
        j--;
    }
    res = max(res,v);
}

例题一: 盛最多水的容器

例题二：和为s的两个数字

快慢指针

思想：
两个指针朝着同一方向前进，一个指针走得慢，一个指针走得快。

例题一：链表的中间结点

例题二：最长连续不重复子序列

209. 长度最小的子数组

209. 长度最小的子数组

核心思想：快慢指针，

1. 当窗口内的和还小于目标值时，移动右指针增大窗口内子数组的和使其大于等于目标值

2. 当窗口内的和已经大于目标值时，移动左指针缩小窗口大小找长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int res=1e9;
        vector<int> s(n+1,0);
        for(int i=1;i<=n;i++){
            s[i] = s[i-1] + nums[i-1];
        }
        if(s[n] < target) return 0;
        int l=0;
        for(int r=0;r<n;){
            if( (s[r+1] - s[l]) >= target){
                res = min(res,r+1-l);
                l++;
            }
            else{
                r++;

            }
        }
        return res;
    }
};

76. 最小覆盖子串

核心思想：

1. 滑动窗口的双指针
2. unordered_map 哈希表存储字符和其对应个数，以此来比较是否覆盖了另一个子数组
3. 下方解法会TLE

class Solution {
public:
    unordered_map<char,int> st,sw;
    bool check(string t,int m){
        bool flag = true;
        for(int i=0;i<m;i++){
            //这里不是等于而是小于（如题意中的我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。）
            if(sw[t[i]] < st[t[i]]){
                flag = false;
                break;
            }
        }
        return flag;
    }
    string minWindow(string s, string t) {
        int n = s.size(); int m = t.size();
        int l=0;
        for(int i=0;i<m;i++){
            st[t[i]] ++;
        }
        int res=10010; int minl,minr;
        bool flag = false;
        for(int r=0;r<=n;){ //这里r到n，是为了满足如果r最后移动到数组末尾时刚好check成功了，但无法更新的minr和minl；因此让它多循环一次
            if(check(t,m)){
                if(r-l < res){
                    flag = true;
                    res = r-l;
                    minr = r;
                    minl = l;
                }
                sw[s[l]] --;
                l++;
            }
            else{
                if(r == n) break; //防止数组越界
                sw[s[r]] ++;
                r++;
            }
        }
        //check函数一次都没有true过 ，则代表无结果的情况，返回空串
        if(flag == false){
            string s = "";
            return s;
        }

        string ans; int idx=0;
        for(int i=minl;i<minr;i++){
            ans.push_back(s[i]);
            idx++;
        }
        return ans;
    }
};