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

raylan.chen大约 2 分钟

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (p == null || p.length() == 0) return new ArrayList<Integer>(0);
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();
        Set<Character> set1 = new HashSet<>();
        // p 使用set1存储，方便后续 O(1) 查找元素
        // p 是否有重复字符？
        for (char c : cp) {
            set1.add(c);
        }
        Set<Character> set2 = new HashSet<>();
        List<Integer> res = new ArrayList<>();
        // 滑动窗口，i记录窗口左边界，j为右边界，set2存储元素防止重复
        for (int i = 0, j = 0; i < cs.length && j < cs.length; j++) {
            // cs[j] 不是 p 包含的元素
            if (!set1.contains(cs[j])) {
                i = j + 1;
                set2.clear();
            } else {
                // cs[j] 是 p 包含的元素，添加到set2
                boolean b = set2.add(cs[j]);
                // 添加失败（已添加过）
                if (!b) {
                    while (cs[i] != cs[j]) {
                        set2.remove(cs[i++]);
                    }
                    i++;
                }
                // set2大小 === cp长度
                if (set2.size() == cp.length) {
                    res.add(i);
                    set2.remove(cs[i++]);
                }
            }
        }
        return res;
    }
}

做题时就在疑惑 p 字符串是否存在重复字符，果然遇到 p = "aa" 就输出错误了

输入: s = "baa", p = "aa" ，输出：[]

正确预期结果：[1]

优秀题解

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        // 当字符串s长度<字符串p的长度
        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }
        // 统计字符串p中各字母出现的顺序（题目不要求子字符串中字母排列顺序相同，因此只需统计字母出现的次数）
        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            // 同时也统计字符串s前p.length()个字母的出现次数
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }

        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }
        // 滑动窗口，左边界的字母出现次数-1，再移动窗口
        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/1123971/zhao-dao-zi-fu-chuan-zhong-suo-you-zi-mu-xzin/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

声明两个长度为26的数组，专门用来存储两个字符串中字母出现的次数；其中「存储字符串 s 中字母出现次数的数组」需要使用「滑动窗口」来「控制其统计」的范围，以达到与字符串 p 进行匹配的效果

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

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

参考链接

个人尝试(❌错误)

优秀题解