LeetCode每日两题02：字符串的排列 （均1200道）方法：哈希表-双指针-滑动窗口

解题思路：客观上来说，最终的答案如果是true，则s2中必然存在某个位置 i 使得以 i 开始的子串s2[i … i+len1)是s1的排列。
依次尝试固定以s2中的每一个位置 l 作为左端点开始的len1长度的子串s2[l … l+len1)是否是s1的排列，最终必然不会错过所有的可能性。
如果固定 l 做左端点，尝试失败，继续尝试 l+1 位置，【左右边界都不需要回退】，这是滑动窗口的前提。

通过一个记账本 charCount 做为【总账表】维护s1的词频表；
滑动窗口内每一个右边界字符进入窗口后，【还账】：charCount[str2[r] - ‘a’]–
如果某个字符多还了（变成负值），即尝试失败，开始尝试下一个左端点（l++）;
左边界字符出窗口后，表示【重新赊账】：charCount[str2[l] - ‘a’]++
最终如果欠账还足了（窗口长度达到len1），则尝试成功，直接返回true。

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int len1 = s1.length();
        int len2 = s2.length();
        int[] charCount = new int[26]; // 【总欠账表】：s1的词频表
        for (char c : str1) { // 统计s1的词频
            charCount[c - 'a']++;
        }
        int l = 0, r = 0; // 滑动窗口左右边界
        // 依次尝试固定以s2中的每一个位置l作为左端点开始的len1长度的子串s2[l ... l+len1)是否是s1的排列
        while (l <= len2 - len1) { // 固定左端点只需要尝试到len2-len1即可
            // 右边界s2[r]字符进入窗口【还账】
            while (r < l + len1 && charCount[str2[r] - 'a'] >= 1) {
                charCount[str2[r] - 'a']--; // 【"还账"】
                r++;
            }
            if (r == l + len1) return true;
            // 左边界s2[l]字符出窗口【赊账】，l++，开始尝试固定下一个位置做左端点
            charCount[str2[l] - 'a']++; // 重新【"赊账"】
            l++;
        }
        return false; // 所有的左端点均尝试还账失败，不可能再有答案了
    }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26