567. 字符串的排列

567. 字符串的排列

滑动窗口

由于输入的字符只包含小字字母，所以可以使用长度为 26 的数组记录字符出现次数，窗口每次向右滑动一格，只需要加减出窗和入窗字符的出现次数

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // 如果s1的长度比s2大，直接返回false
        if (s1.length() > s2.length()) return false;
        // 存放字符出现次数
        int[] char1 = new int[26];
        int[] char2 = new int[26];
        // 初使根据 s1 长度初使化
        for (int i = 0; i < s1.length(); i++) {
            char1[s1.charAt(i) - 'a']++;
            char2[s2.charAt(i) - 'a']++;
        }
        // 如果初使化后就相同，直接返回
        if (Arrays.equals(char1, char2)) return true;
        // 从第二个字符开始往后遍历
        for (int i = 1; i < s2.length() - s1.length() + 1; i++) {
            // 注意这里每次只需要处理出窗和入窗字符
            // 出窗字符
            char2[s2.charAt(i - 1) - 'a'] --;
            // 入窗字符
            char2[s2.charAt(i + s1.length() - 1) - 'a'] ++;
            if (Arrays.equals(char1, char2)) return true;
        }
        return false;
    }
}