滑动窗口算法实战：从最大连续 1 到最小覆盖子串

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

以示例 1 为例，p 可以重排为 abc、acb 等。我们需要在 s 中找到所有与 p 互为异位词的子串起始索引。

判断异位词的核心是字符频次一致。暴力解法是每次截取长度相同的子串重新统计哈希表，效率较低。优化的关键在于利用滑动窗口：窗口大小固定为 p 的长度。

维护两个计数数组（或小哈希表），分别记录 p 的字符频次和当前窗口的字符频次。为了进一步优化，引入变量 count 统计'有效匹配字符数'。当窗口内某字符数量达到 p 中该字符的数量时，count 增加；移出窗口时相应减少。当 count 等于 p 的长度时，说明找到了一个异位词。

由于题目限定小写字母，使用长度为 26 的整型数组比 HashMap 更高效，时间复杂度可降至 O(n)。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        int[] hash1 = new int[26];
        for (char ch : pp) {
            hash1[ch - 'a']++;
        }
        int[] hash2 = new int[26];
        int count = 0;
        for (int left = 0, right = 0; right < s.length(); right++) {
            char in = ss[right];
            if (++hash2[in - 'a'] <= hash1[in - 'a']) {
                count++;
            }
            if (right - left + 1 > p.length()) {
                char out = ss[left++];
                if (hash2[out - 'a']-- <= hash1[out - 'a']) {
                    count--;
                }
            }
            if (count == p.length()) {
                ret.add(left);
            }
        }
        return ret;
    }
}

1.3. 串联所有单词的子串

这道题要求找出 s 中包含 words 数组中所有单词（每个单词出现次数需一致）的子串。

与上一题类似，但处理对象变成了单词而非字符。这里需要使用 Map 来映射单词及其频次。关键点在于指针的移动步长：right 指针不应每次移动一个字符，而应移动 words 中单词的长度 len。

此外，由于起始位置不同可能导致匹配失败，我们需要对 s 进行多次滑动窗口遍历，起始偏移量从 0 到 len-1 即可覆盖所有情况。这样避免了重复计算，保证了效率。

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        Map<String, Integer> hash1 = new HashMap<>();
        for (String str : words) {
            hash1.put(str, hash1.getOrDefault(str, 0) + 1);
        }
        int len = words[0].length(), m = words.length;
        for (int i = 0; i < len; i++) {
            Map<String, Integer> hash2 = new HashMap<>();
            int count = 0;
            for (int left = i, right = i; right + len <= s.length(); right += len) {
                String in = s.substring(right, right + len);
                hash2.put(in, hash2.getOrDefault(in, 0) + 1);
                if (hash2.get(in) <= hash1.getOrDefault(in, 0)) {
                    count++;
                }
                if (right - left + 1 > len * m) {
                    String out = s.substring(left, left + len);
                    if (hash2.get(out) <= hash1.getOrDefault(out, 0)) {
                        count--;
                    }
                    hash2.put(out, hash2.get(out) - 1);
                    left += len;
                }
                if (count == m) {
                    ret.add(left);
                }
            }
        }
        return ret;
    }
}

1.4. 最小覆盖子串

目标是在 s 中找到包含 t 所有字符的最短子串。若不存在则返回空字符串。

同样采用滑动窗口策略。right 指针扩张直到窗口包含 t 的所有字符（即满足覆盖条件），此时尝试收缩 left 指针以缩短窗口长度，同时保持覆盖条件成立。记录过程中的最小长度及起始位置。

为了快速判断是否满足条件，我们不再每次都遍历哈希表比较，而是维护一个变量 kinds 记录 t 中不同字符的种类数，以及 count 记录当前窗口中已满足频次要求的字符种类数。当 count 等于 kinds 时，说明窗口合法。

注意边界处理，如 begin 未更新时返回空串。

public class Solution {
    public String minWindow(String s, String t) {
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        int[] hash1 = new int[128];
        int kinds = 0;
        for (char ch : tt) {
            if (hash1[ch]++ == 0) {
                kinds++;
            }
        }
        int[] hash2 = new int[128];
        int minlen = Integer.MAX_VALUE;
        int begin = -1;
        for (int left = 0, right = 0, count = 0; right < ss.length; right++) {
            char in = ss[right];
            if (++hash2[in] == hash1[in]) {
                count++;
            }
            while (kinds == count) {
                if (right - left + 1 < minlen) {
                    begin = left;
                    minlen = right - left + 1;
                }
                char out = ss[left++];
                if (hash2[out]-- == hash1[out]) {
                    count--;
                }
            }
        }
        if (begin == -1) {
            return "";
        } else {
            return s.substring(begin, begin + minlen);
        }
    }
}