滑动窗口

滑动窗口往往用于求特定类型的最长字串，通过在正确的时机对窗口进行平移或扩张来获得最大值。

例题

无重复字符的最长字串

题目

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

示例 1:

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

示例 2:

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

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

分析

题目要求不能有重复字符，所以我们想象现在有一个窗口，透过窗口你可以看到字符串的一部分，现在要求这个窗口内的子串不能有重复字符。我们假设当前的窗口内没有重复字符，那么可以尝试将窗口向右扩张一格，如果出现了重复字符，就从左侧开始收缩整个窗口，直到之前出现过的这个字符移到了窗口外侧，然后继续向右扩展这个窗口。在这个过程中窗口的最大值即是最长字串的长度（因此每次更新窗口大小的时候都要记录以确定最大值）

代码如下

class Solution {
    public int lengthOfLongestSubstring(String s) {
        boolean[] happen = new boolean[256];
        int left = 0, max = 0; // 左边界, 最大值
        char[] tmp = s.toCharArray();
        for (int right = 0; right < tmp.length; right++) {
            char c = tmp[right];
            if (happen[c]) {
                // 重复, 收缩左边界, 直到c被排除
                while (tmp[left] != c) {
                    char real = tmp[left++];
                    happen[real] = false; // 收缩时把那些出现一次的字符的标记（happen）置为false（窗口里一定只有仅出现一次的字符）
                }
                // 现在left指向前一个c, 去除
                left++;
            }
            happen[c] = true;
            // 记录并更新可能的最大值
            max = Math.max(max, right - left + 1);
        }
        return max;
    }
}

找到字符串中所有字母异位词

题目

给定两个字符串 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 * 104
• s 和 p 仅包含小写字母

分析

首先根据异位词的定义，我们只需要保证这个子串和目标字符串的构成字符一致即可，即维护一个窗口，保证窗口中的所有字符和串 $p$ 的所有字符一致即可。串 $p$ 的特征可以用一个$26$位长的数组来表示，即每个字符出现的次数，之后维护窗口时动态的更新另一个用于记录窗口字符信息的$26$位数组，当这两个数组的内容一致时，我们认为找到了这个重排形成的字符串，即窗口框住的串。

需要注意一些细节来优化性能：

• 当某个字符出现的次数大于目标串中该字符的出现次数时，该窗口的内容一定不可能满足，此时要收缩窗口左边界直到该字符满足出现次数要求
• 当某个字符出现的次数小于或等于目标串中该字符的出现次数时，如果还没匹配上，则窗口需要继续向右扩张

代码如下

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        char[] sArr = s.toCharArray(), pArr = p.toCharArray();
        int[] count = new int[26];
        int[] countTmp = new int[26];
        for (char c : pArr) {
            count[c - 'a']++;
        }
        int left = 0;
        for (int i = 0; i < sArr.length; i++) {
            countTmp[sArr[i] - 'a']++;
            if (countTmp[sArr[i] - 'a'] > count[sArr[i] - 'a']) {
                while (left < i && sArr[left] != sArr[i]) {
                    countTmp[sArr[left] - 'a']--;
                    left++;
                }
                countTmp[sArr[left] - 'a']--;
                left++;
            }
            if (checkTwoArr(countTmp, count)) {
                ans.add(left);
            }
        }
        return ans;
    }

    boolean checkTwoArr(int[] a, int[] b) {
        if (a.length == b.length) {
            for (int i = 0; i < a.length; i++) {
                if (a[i] != b[i]) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }
}

(•‿•)