🌕 🌗 438. 找到字符串中所有字母异位词

难度: 🌕 🌗

• 问题描述
• 解法
• 输出

问题描述

---

解法

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // 思路:
        // 数组做 map
        List<Integer> res = new ArrayList<>();
        int len = s.length();
        int n = p.length();
        if(len < n) {
            return res;
        }
        int[] map = new int[26];
        for(char c : p.toCharArray()) {
            int index = c - 'a';
            map[index] ++;
        }
        // 滑动窗口遍历 s 找异位词子串
        int[] array = new int[26];
        int left = 0;
        int right = 0;
        while(right < len) {
            // 向右遍历达到 p 字符串长度
            while(right < len && right <= left + n - 1) {
                int index = s.charAt(right) - 'a';
                if(map[index] > 0) {
                    array[index] ++;
                }
                right ++;
            }
            // right < len && 长度 == n
            // 判断当前是否满足条件
            if(Arrays.equals(map, array)) {
                res.add(left);
            }
            if(right >= len) {
                return res;
            }            
            // 左边界缩进一格
            int tmpIndex = s.charAt(left) - 'a';
            if(map[tmpIndex] > 0 && array[tmpIndex] > 0) {
                array[tmpIndex] --;
            }
            left ++;
        }
        return res;
    }
}

---

输出