滑动窗口

简而言之，滑动窗口算法在一个特定大小的字符串或数组上进行操作，而不在整个字符串和数组上操作
这样就降低了问题的复杂度，从而也达到降低了循环的嵌套深度
其实这里就可以看出来滑动窗口主要应用在数组和字符串上

简介

滑动窗口常常用于解决下面这些问题：
可以用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。
由于区间连续，因此当区间发生变化时，可以通过旧有的计算结果对搜索空间进行剪枝
这样便减少了重复计算，降低了时间复杂度

也就是说，对于“ 请找到满足 xx 的最 x 的区间（子串、子数组）的 xx ”这类问题，我们就用它

大体框架

滑动： 说明这个窗口是移动的，也就是移动是按照一定方向来的。

窗口： 窗口大小并不是固定的，可以不断扩容直到满足一定的条件；也可以不断缩小，直到找到一个满足条件的最小窗口；当然也可以是固定大小

1.我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。

2.我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

3.此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）
同时，每次增加 left，我们都要更新一轮结果。

4.重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

对于2，3步的条件判断以及更新、条件缩小/扩大，都可以看情况而定

实际上，这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解
左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

伪代码框架

对于非固定大小的滑动窗口，可以简单地写出如下伪码框架： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string s, t;
// 在 s 中寻找 t 的「最小覆盖子串」
int left = 0, right = 0;
string res = s;

while(right < s.size()) {
    window.add(s[right]);
    right++;
    // 如果符合要求，说明窗口构造完成，移动 left 缩小窗口
    while (window 符合要求) {
        // 如果这个窗口的子串更短，则更新 res
        res = minLen(res, window);
        window.remove(s[left]);
        left++;
    }
}
return res;

但是，对于固定窗口大小，可以总结如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 固定窗口大小为 k
 string s;
 // 在 s 中寻找窗口大小为 k 时的所包含最大元音字母个数
 int  right = 0;
 while(right < s.size()) {
     window.add(s[right]);
     right++;
     // 如果符合要求，说明窗口构造完成，
     if (right>=k) {
         // 这是已经是一个窗口了，根据条件做一些事情
        // ... 可以计算窗口最大值等 
         // 最后不要忘记把 right -k 位置元素从窗口里面移除
     }
 }
 return res;

题目

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = “ab” s2 = “eidbaooo”
输出：true
解释：s2 包含 s1 的排列之一 (“ba”).

示例 2：

输入：s1= “ab” s2 = “eidboaoo”
输出：false

提示：

1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母

字符串子串排列

无论是怎么个解法，我们先要确定一件事情：
“s1 的排列之一是 s2 的 子串”意味着说明，实质上它等同于：
s1中字符出现的频率，等于s2某一字串中字符出现的频率

按照这个思路就好做了，只是麻烦和复杂度的问题

当然，别搞暴力破解

我们利用两个大小为26的数组，记录频率，分别是ct1,ct2
而后比较二者频率即可 

1
2
//关于如何记录频率这件事
ct1[s1.charAt(i) - 'a']++;

得到的字符，减去’a’，即可获得对应的差值(ASCII)，差值为0就是a，1就是b，以此类推
因为我们规定了，只含小写字母，所以这样就可以记录字符的出现频率了

下面我们按照思路完整的来一次 

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
    class Solution {
    public boolean checkInclusion(String s1, String s2) {
        //首先先得到两个字符串的长度
        int n = s1.length();
        int m = s2.length();
        int []ct1 = new int[26] ; 
        int []ct2 = new int[26] ; 

        //如果s1更长，那么就直接返回false
        if(n>m)
            return false ; 

        for(int i = 0 ; i<n;i++){
            //第一次得到二者频率并且比较
            ct1[s1.charAt(i) - 'a']++; 
            ct2[s2.charAt(i) - 'a']++;
        }

        if(Arrays.equals(ct1,ct2)){
            return true ; 
        }

        for(int i = n ; i < m ; i++)
        {
            //不断移动s2的频率集，得到答案
            ct2[s2.charAt(i) - 'a']++;//首位增加
            ct2[s2.charAt(i-n) - 'a']--;//末尾减少

            if(Arrays.equals(ct1,ct2)){
                return true ; 
            }
        }

        return false ; 

    }
}

在

1
2
3
4
5
for(int i = 0 ; i<n;i++){
    //第一次得到二者频率并且比较
    ct1[s1.charAt(i) - 'a']++; 
    ct2[s2.charAt(i) - 'a']++;
}

中，我们分析的两者最开始的情况，也就是ct2还没有开始滑动的情况
其实也包含了ct1,ct2一开始就能匹配的情况

之后，我们开始滑动ct2，具体表现就是：把新来的频率记录，末位的频率淘汰： 

1
2
3
4
5
6
7
8
9
10
for(int i = n ; i < m ; i++)
{
    //不断移动s2的频率集，得到答案
    ct2[s2.charAt(i) - 'a']++;//首位增加
    ct2[s2.charAt(i-n) - 'a']--;//末尾减少

    if(Arrays.equals(ct1,ct2)){
        return true ; 
    }
}

当然啦，每次执行完要记得检查条件，要是匹配上了就跳出来

寻找不重复的最长字符串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

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

示例 2:

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

题解

什么是滑动窗口？
在这里，它其实就是一个队列,比如例题中的 abcabcbb
进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。
所以，我们要移动这个队列,不断搜寻，扩大，得到结果。
如何移动？
我们可以不断向前扩大，直到到达底部
当我们碰到了某个和队列中的元素相同的元素的时候，意味着这串字符串失败了
于是我们要移动窗口，重新寻找，此时只要把队列的左边的元素移出就行了.

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
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0)
            return 0;
        //字符串长度为0，那么就只能得到0的结果

        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0; //最大值计数
        int left = 0;
        //left是左边界，用于控制窗口和计算长度  

        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i)) + 1);
                //如果我们得到了某个字符，而我们的map中已经包含它了，那么我们就移动left 
                //左移一位就行:因为之前的字符串是在s.charAt(i)这个字符这里重复了
                //那么说明在这个字符之前的字符串无论怎么分，都有会发生这个重复事件  
                //而"发生重复事件"之前的最大长度，我们已经记录下来了
                //那么我们就在最新的这个重复字符，也就是s.charAt(i)之前，重新开始记录   
                //于是新起点定为map.get(s.charAt(i)) + 1)   
            }
            map.put(s.charAt(i),i);
            //无论怎么样都把新字符入表，记录的是"字符-下标"的键值对 
            max = Math.max(max,i-left+1);
            //每一轮操作都更新最大值
        }
        return max;
        
    }
}