LeetCode 题解
    567. Permutation in String 字符串中的组合

    567. Permutation in String 字符串中的组合

    描述：给定字符串 s1 和 s2，问在 s2 的子串中是否有能通过 s1 的排列组合得到的

    解法一：定长数组滑动 12ms

    子串和 s1 会有相同的哈希签名，每往前滑动一格，子串签名只需要加上下一字符的计数和减去第一个字符的计数，每滑动一格就比较一次签名

    时间复杂度：O(n) 空间复杂度：O(1)

    bool checkInclusion(string s1, string s2) {
    if (s1.size() > s2.size()) return false;
    if (s1 == s2) return true;
    bool res = false;

    int hash[26] = {0};
    int h[26] = {0};
    int i;
	// Hash签名生成
    for(i=0;i<s1.size();++i) {
        hash[s1[i]-'a']++;
        h[s2[i]-'a']++;
    }

    while(true) {
        res = true;
		// 比较签名，相同则存在
        for(int j=0;j<26;j++) {
            if (hash[j] != h[j]) {
                res = false;
                break;
            }
        }

        if (res) return true;
        if (i == s2.size()) break;

		// 滑动一格，签名减头加尾
        h[s2[i-s1.size()]-'a']--;
        h[s2[i++]-'a']++;
    }

    return false;
}

    解法优化：双指针维护滑动窗口 8ms

    由签名相同的比较转化成滑动窗口内的子串在哈希签名中还能够减 没得减就尽量滑得远一点

    时间复杂度：O(n) 空间复杂度：O(1)

    bool checkInclusion(string s1, string s2) {
    int h[26] = {0};
    for(int i=0;i<s1.size();++i) ++h[s1[i]-'a'];
    int win_size = s1.size();

    for(int start=0, end = 0;end<s2.size();++end) {
        if (h[s2[end]-'a'] > 0) --win_size;
        --h[s2[end]-'a'];

        while (win_size==0) {
			// 窗口刚好为子串长度，找到
            if (end-start+1 == s1.size()) return true;
			// 需要往前滑动，只有找到有的字符才继续把 end 往前滑
            if (++h[s2[start]-'a'] > 0) win_size++;
            start++;
        }
    }
    return false;
}

     证明：为什么end永远都会大于start ?

    因为 end 先进行遍历，先减掉子串大小的的哈希值，start 开始滑动之前 end 一定已经确定了目标一定在 s2[start...end] 之间，剩下的就是通过递增 start 来缩小区间范围，范围长度等于子串长度，就相当于是找到

    摘录一段英文的解释： i 是 start，j 是 end @ 1. try find a window (i, j) where s2.substr(i, j + 1 - i) contains all chars in s1; @ 2. once found, try reduce window(i, j) such that j + 1 - i == s1.size() while the window still contains all chars in s1 by moving i, return true; @ 3. if windows no longer contain all chars in s1, keep moving j forward;

    #滑动窗口 #双指针

    503. Next Greater Element II60. Permutation Sequence 第 K 个字典序排列