leetcode 438. 找到字符串中所有字母异位词 -java

给定两个字符串 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 仅包含小写字母

思路：用滑动窗口法，思路就是把p当作一个窗口，首先要统计这个窗口内所有字母及字母出现的频率，再对s使用滑动窗口，统计窗口内存在这些字母且这些字母出现的频率和p的出现频率相同的窗口，这些窗口左边框的下标就是需要的子串的起始索引

代码

        List<Integer> indexList = new ArrayList<>();

        // 获取字符串 s 和 p 的长度
        int slen = s.length();
        int plen = p.length();

        // 如果p的长度小于s的长度 - 不存在异位词
        if (slen < plen) {
            return indexList;
        }

        // 用于存储字符串p的每个字母的存在频率
        int[] pCount = new int[26];
        // 用于存储字符串s的每个字母的存在频率
        int[] sCount = new int[26];

        // 将两个字符串处理为字符数组
        char[] pChars = p.toCharArray();
        char[] sChars = s.toCharArray();
        // 获取p中所有字母出现频率 - 获取s中开头第一个窗口字母出现频率
        for (int i = 0; i < plen; i++) {
            pCount[pChars[i]-'a']++;
            sCount[sChars[i]-'a']++;
        }

        // 如果起始窗口就满足异位 - 索引累加 0
        if (Arrays.equals(pCount,sCount)) {
            indexList.add(0);
        }

        // 进行窗口的右滑 右边框从第一个位置开始
        for (int i = plen; i < slen; i++) {
            // 每滑动一位，将左边框掠过的字母的频率-1
            sCount[sChars[i-plen]-'a']--;
            // 将右边框框住的字母的频率+1
            sCount[sChars[i]-'a']++;

            // 判断 sCount 和 pCount 相同， 即框内所有字母出现频率相同， 则s出现p的异位词
            if (Arrays.equals(sCount,pCount)) {
                // 起始索引就是左边框的下标
                indexList.add(i-plen+1);
            }
        }

        return indexList;