双指针滑动窗口算法

滑动窗口

最常见的滑动窗口其实就是我们字符串匹配或者计算机网络中流量控制的窗口。

1. 通过维护一个滑动窗口来找到一个target比如找一个子串，窗口可变，但是长度一定和target一直，比如符合要求，就扩大窗口将字符串加入进来
2. 通过窗口找到一个最长子串的问题，窗口可变的，动态的找一个最大的值
3. 固定窗口，主要是通过窗口来限制流量，比如窗口大小为100，发送[1,9999]的数据，如果i为x，那么j最大为x+99。同理，如果j为y，i最小为y-99，如果不是上述问题。如果i，j维护的窗口小于的话，可以加速发送数据包；如果超过了，要么是发的太快了，要么是有的数据包发送后没有发送ack确认，所以要重传。

3.找无重复最长子串

问题描述

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

代码

int lengthOfLongestSubstring(string s) {int res=0;unordered_map<char,int>mp;int i=0,j=0;while(j<s.size()){char c=s[j];j++;mp[c]++;//1.加入窗口while(i<j&&mp[c]>=2)//2.查看窗口是否满足条件，不满足条件就让左端的退出，然后窗口维持的数据对应的减少。{char tmp=s[i];i++;mp[tmp]--;}res=max(res,j-i);}return res;
}

438找到所有字符串中的异位数字

题目

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

1 <= s.length, p.length <= 3 * 10e4
s 和 p 仅包含小写字母

注意题干要求，一般支持用空间换时间的方法，都是的空间复杂度都不超过10e5

分析

1. 这个题目是固定窗口还是非固定窗口？很显然这个题目是固定窗口的方法，因为子串是固定的，也是是target我们要解决的问题
   1. 上一题，我们找s传中最长的无重复连续子串，这个就不是固定的，因为这里滑动窗口维持的是字符串不重复，而我们本题所做的是找窗口大小为p.size()内是否是异位字符串
2. 如何解决窗口大小为p.size()内是否是异位字符串，我们要么维护一个valid来记录是否符合异位字符串标准。要么，p用一个mp或者长度为26的vector来记录不同字符的大小。然后毕竟比较mp或者vector是否相同，这么做至少要遍历26次，如果能维护一个valid，只需要做一次条件判断即可

代码

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;vector<int> findAnagrams(string s, string p) {vector<int>res;unordered_map<char,int>ms,mp;for(auto pi:p)mp[pi]++;int i=0,j=0;int valid=0;while(j<s.size()){char  c=s[j];j++;if(mp.count(c)){ms[c]++;if(ms[c]==mp[c]){valid++;}}while(j-i==p.size()){if(valid==mp.size()){res.push_back(i);}char d=s[i];i++;if(mp.count(d)){if(mp[d]==ms[d]){valid--;}ms[d]--;}}}return res;
}int main()
{string s="cbaebabacd";string p="abc";vector<int> res=findAnagrams(s,p);cout<<"sort "<<endl;for(auto &r:res){cout<<r<<"_";}cout<<"end:"<<endl;return 0;
}