滑动窗口(Sliding Window)是双指针算法中的一类题型(子集)，即双指针≥滑动窗口

例题1.无重复字符的最长子串

思路

维护一个变长窗口，利用哈希表来统计每个字符出现的次数
前一个指针不断向前移动，如果窗口中出现重复字符，则把窗口尾部缩短，直到窗口内没有重复字符

双指针一般具有单调性：i往后走时，j一定是往后走的
证明：
假设[j,i]之间没有重复字符，i往前走到i'，j往后走到j'
如果[j',i']是没有重复字符的，则[j',i]是以i为结尾的没有重复字符的子串，j'<j，与[i,j]是最长无重复字符子串矛盾

Java代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        char[] c = s.toCharArray();
        int n = c.length;
        int[] hash = new int[128];
        for(int i = 0, j = 0; i < n; i++){
            hash[c[i]]++;
            while(hash[c[i]] > 1) hash[c[j++]]--;
            res = Math.max(res,i-j+1);
        }
        return res;
    }
}

例题2.字符串的排列

思路

这题是一道定长滑动窗口的问题
我们可以利用一个哈希表统计出s1串中各字符出现的次数
遍历s2串，如果碰到在s1串中出现的字符，则哈希表对应位置的次数减1
1.
    如果这个字符在异位词中没有出现过，则会被减到负数
    如果出现过，则减到0时说明窗口中已经满足了某一个字符的匹配，匹配字符数量+1
2.
    如果窗口长度比异位词长度更长，则移除窗口尾部元素，并且更新哈希表
    如果更新哈希表之前，对应位置的哈希表值为0，说明删除之前窗口里的最后一个字符是满足要求的
    删除后，则该字符的数量不满足要求，匹配字符数量-1

如何判定出现了s1串的异位词呢？
我们可以利用一个变量来统计窗口中匹配异位词的字符个数，如果此个数与异位词中出现的个数相同，则输出答案

Java代码

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if(s1.length() > s2.length()) return false;
        int[] hash = new int[26];
        for(char c: s1.toCharArray()){
            hash[c-'a']++;
        }
        int tot = 0;
        for(int i = 0; i < 26; i++){
            if(hash[i] != 0) tot++;
        }
        char[] c = s2.toCharArray();
        int cnt = 0;
        for(int i = 0, j = 0; i < s2.length(); i++){
            if(--hash[c[i]-'a'] == 0) cnt++;
            if(i-j+1 > s1.length()){
                if(hash[c[j]-'a'] == 0) cnt--;
                hash[c[j++]-'a']++;
            }
            if(cnt == tot) return true;
        }
        return false;
    }
}

例题3.找到字符串中的所有字母异位词

思路

这题和上一题完全一样，只不过要记录所有方案，不需要提前退出循环

Java代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] hash = new int[26];
        for(char c: p.toCharArray()){
            hash[c-'a']++;
        }

        int target = 0;
        for(int i = 0; i < 26; i++){
            if(hash[i] != 0) target++;
        }

        int cnt = 0;
        List<Integer> res = new ArrayList<>();
        char[] ss = s.toCharArray();
        for(int i = 0, j = 0; i < ss.length; i++){
            if(--hash[ss[i]-'a'] == 0) cnt++;
            if(i-j+1 > p.length()){
                if(hash[ss[j]-'a'] == 0) cnt--;
                hash[ss[j++]-'a']++;
            }
            if(cnt == target) res.add(j);
        }
        return res;
    }
}

• 顺便贴一个比较投机取巧的办法，直接用内置函数比较哈希表是否相同

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if(p.length() >= s.length()) return new ArrayList<>();
        int[] hashs = new int[26];
        int[] hashp = new int[26];
        for(char c: p.toCharArray()){
            hashp[c-'a']++;
        }
        char[] c = s.toCharArray();
        List<Integer> res = new ArrayList<>();
        for(int i = 0, j = 0; i < c.length; i++){
            if(i >= p.length()){
                hashs[c[i]-'a']++;
                hashs[c[i-p.length()]-'a']--;
            }else{
                hashs[c[i]-'a']++;
            }
            if(Arrays.equals(hashs,hashp)){
                res.add(i-p.length()+1);
            }
        }
        return res;
    }
}