两道题解决滑动窗口问题

定长

567. 字符串的排列 - 力扣（LeetCode）

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

解题思路

1° 传统套路就是定义两个哈希表，一个存储s1中每个字符的出现次数，记s1的长度为n，另外一个按n的步长遍历s2，并将每次的结果存储这个哈希表中，两哈希表进行比对，若相同则直接return true，若不等，清空s2的哈希表，继续遍历，直到s2遍历完，若不存在，return false。

2° 基于上述题解，我们可以采用滑动窗口模板进行优化。思路是把比对两个哈希表的过程 => 一个哈希 + 一个遍变量 diff == 0？ 

3° 同样，记s1的长度为n，以n为一个“窗口”，对于哈希表cnt，把s1出现过的字符--，s2出现过的字符++

4° 遍历哈希表cnt，如果cnt[i] != 0，说明存在不同字符，diff值++，若最终得到的diff==0，说明不存在不同字符，直接return true，否则则从s2的位置n继续遍历

5° 我们需声明两个变量存储每次滑动的离开字符，和新进入的字符，如果离开字符离开窗口之前，cnt[这个字符]==0，说明这个字符之前是平衡的（即s1，s2中这个字符的出现次数相等）,字符离开后，则打破了这个平衡，所以diff要++。且cnt[这个字符]--，再次检查离开字符离开之后，cnt[这个字符]==0? 说明这个字符离开后就平衡了，所以diff--，新进入的字符同理。

6° 当窗口滑动过程中出现diff==0，说明s2存在包含s1的子字符串，return true，遍历完仍没有找到则return false

代码实现

bool checkInclusion(char* s1, char* s2) {
    int n = strlen(s1), m = strlen(s2);
    if(n > m){
        return false;
    }
    int cnt[26] = {0};
    for(int i = 0; i < n; i++){
        cnt[s1[i]-'a']--;
        cnt[s2[i]-'a']++;
    }
    int diff = 0;
    for(int i = 0; i < 26; i++){
        if(cnt[i]!=0){
            diff++;
        }
    }
    if(diff==0){
        return true;
    }
    for(int i = n; i < m; i++){
        int x = s2[i]-'a', y = s2[i-n]-'a';
        if(x==y){
            continue;
        }
        if(cnt[x]==0){
            diff++;
        }
        cnt[x]++;
        if(cnt[x]==0){
            diff--;
        }
        if(cnt[y]==0){
            diff++;
        }
        cnt[y]--;
        if(cnt[y]==0){
            diff--;
        }
        if(diff==0){
            return true;
        }
    }
    return false;
}

不定长

面试题 17.18. 最短超串 - 力扣（LeetCode）

假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。

返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。

解题思路

思路大体上同上一题，由hash[small[i]]++, hash[big[i]]--, 和 count == 0 ？来维护滑动窗口，只不过这题是不定长的。需要维护count==0的同时，从窗口的左边开始缩短以求得最短超串。

代码实现

#define MAX_SIZE 1000000
int* shortestSeq(int* big, int bigSize, int* small, int smallSize, int* returnSize){
    int* ret = (int*)calloc(2, sizeof(int));
    ret[0] = 0;
    ret[1] = INT_MAX;
    int* hash = (int*)calloc(MAX_SIZE, sizeof(int));  
    int count = 0;
    int j = 0;
    for (int i = 0; i < smallSize; i++) {
        hash[small[i]]++;
        count++; 
    }
    for (int i = 0; i < bigSize; i++) {
        hash[big[i]]--;  
        if (hash[big[i]] == 0)
            count--; 
        // 如果统计的不同元素的数量为0，即找到了包含'small'数组中所有元素的子数组，开始压缩窗口
        while (!count) {  
            hash[big[j]]++; 
            if (hash[big[j]] > 0) {
                count++;
                if (ret[1] - ret[0] > i - j) { 
                    ret[0] = j;
                    ret[1] = i;
                }
            }
            j++;
        } 
    }
    *returnSize = ret[1] != INT_MAX ? 2 : 0;
    return ret;
}