滑动窗口

中间一些步骤很好的诠释了“滑动窗口”的思想

题目

给你两个字符串 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
而后比较二者频率即可

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

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

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

    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 ; 

    }
}

在

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

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

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

        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 ; 
            }
        }

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