【算法笔记】力扣热题100（LeetCode hot-100）438. 找到字符串中所有字母异位词 滑动窗口

力扣热题100（LeetCode hot-100）之 438. 找到字符串中所有字母异位词

本文主要记录算法思路，着急要答案的同学可以直接跳转到最后的代码。

题目

给定两个字符串 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" 的异位词。

题解

求什么？

我们需要找到字符串 s 中所有是 p 的字母异位词的子串，并返回这些子串的起始索引。
异位词换句话说就是：两个字符串的字符相同，但排列顺序不一定相同的字符串。

这个问题，一般怎么解？

思路：

一般来说，我们可以使用滑动窗口（Sliding Window）的方法来解决这个问题。
滑动窗口就是指定一个大小作为窗口，然后在字符串上滑动这个窗口，找到符合条件的子串。

1. 定义两个数组 sWinFlag 和 pFlag，分别记录窗口中和 p 中各个字符的数量。
2. 初始化窗口，统计第一个窗口中各个字符的数量。
3. 滑动窗口，更新窗口中各个字符的数量。
4. 如果窗口中的字符数量和 p 中的字符数量一样，说明是异位词，记录起始索引

答案

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();
        // 如果s的长度小于p的长度，直接返回空列表
        if (sLen < pLen) {
            return Collections.emptyList();
        }
        int[] sWinFlag = new int[26]; // 用于记录窗口中各个字符的数量
        int[] pFlag = new int[26]; // 用于记录p中各个字符的数量
        for (int i = 0; i < pLen; i++) {
            sWinFlag[s.charAt(i) - 'a']++;
            pFlag[p.charAt(i) - 'a']++;
        }
        
        List<Integer> res = new ArrayList<>();
        if (Arrays.equals(sWinFlag, pFlag)) { // 单独处理第一个窗口
            res.add(0);
        }
        // 滑动窗口
        for (int left = 0, right = pLen; right < sLen; left++, right++) {
            sWinFlag[s.charAt(left) - 'a']--;
            sWinFlag[s.charAt(right) - 'a']++;
            // 如果窗口中的字符数量和p中的字符数量一样，说明是异位词
            if (Arrays.equals(sWinFlag, pFlag)) {
                res.add(left + 1);
            }
        }
        return res;
    }
}