题目描述

可以使用滑动窗口进行求解

复杂度

时间复杂度为 (O(n)) 空间复杂度为 (O(n))

Java 代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
         Map<Character, Integer> cnt = new HashMap<>();
        for (char c : p.toCharArray()) {
            cnt.put(c, cnt.getOrDefault(c, 0) + 1);
        }

        List<Integer> res = new ArrayList<>();
        int tot = cnt.size(); // 目标字符种类数
        int satisfy = 0; // 当前窗口中满足条件的字符种类数

        // 双指针滑动窗口
        for (int i = 0, j = 0; i < s.length(); i++) {
            // 将当前字符加入窗口，并更新频率
            char c = s.charAt(i);
            cnt.put(c, cnt.getOrDefault(c, 0) - 1);
            if (cnt.get(c) == 0) {
                satisfy++; // 如果某个字符频率达到目标值，满足种类数增加
            }

            // 当窗口大小超过 p 的长度时，收缩左边界
            while (i - j + 1 > p.length()) {
                char d = s.charAt(j);
                if (cnt.get(d) == 0) {
                    satisfy--; // 如果移出的字符频率不再满足，减少满足种类数
                }
                cnt.put(d, cnt.get(d) + 1); // 更新频率
                j++; // 移动左指针
            }

            // 如果满足种类数与目标种类数一致，记录左边界
            if (satisfy == tot) {
                res.add(j);
            }
        }

        return res;
    }
}