567. 字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2:
输入: s1= "ab" s2 = "eidboaoo"
输出: False
注意：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间

题解

首先理解子串的概念：字符串中任意个连续的字符组成的子序列称为该串的子串。题目要求判断字符串s1的排列是否为字符串s2的子串，那么可以得出：若是子串，那么字符串s2中存在一个子串，其长度与字符串s1相等，并且子串中每个字符出现的次数与s1相等。
这里使用双指针的解法：定义left，right两个指针，维护一个[left,right]区间，在保证区间内每个字符出现的次数不大于s1每个字符出现的次数的条件下，寻找是否存在一个区间，长度等于s1的长度。

    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        if (n > m) return false;
        int[] count1 = new int[26];    //记录s1各字符出现次数
        int[] count2 = new int[26];    //记录s2各字符出现次数
        for (int i = 0; i < n; i++) {
            count1[s1.charAt(i) - 'a']++;
        }
        int left = 0;
        int right = 0;
        while(right < m){
            char cur = s2.charAt(right);
            int index = cur - 'a';
            count2[index]++;
            while (count2[index] > count1[index]) { //字符频率不同，区间左侧右移
                count2[s2.charAt(left) - 'a']--;//区间最左侧被移出
                left++;
            }
            if (right - left + 1 == n) return true;  //若符合条件,直接返回
            right++;
        }
        return false;
    }