Sliding Window

题型

找满足某一性质的substring/subarray. 分为静态窗口和动态窗口。前者常用于检测是否存在给定字符串的permutation。后者常用于找满足目标性质的最长substring，窗口能达到的长度即答案。

静态窗口

给定一长一短两个字符串，判断短的permutation是否在长的出现。

s1的permutation在s2中意味着s2中某一段有s1中所有元素。因此先把s1中每个元素的count记下来存到一个array里，然后维持一个s1 size的窗口扫描s2，当遇到元素与map中的元素相同时，把相应的count--, 同时把窗口最前面元素剔除并把(如果有的话)相应的count++. 我们可以维持一个当前窗口中包含s1元素的数目curCount，当curCount == s1.length时意味着当前窗口包含了所有s1的元素。当array中所有元素的count都为0时，表明这一段刚好有且仅有s1中所有元素。

Code

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        int[] amount = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            // 滑动窗口: 维持一个和s1等长的窗口, 判断窗口包含的元素是否和s2包含的元素相同
            // 初始把s1中所有元素放入
            // 每次窗口右滑, 看作从中拿出新r, 并把旧l的字符还回去
            // 正值表示该字符还没有被取完
            // 0表示刚好.
            // 负值表示该字符取过头了.
            amount[s1.charAt(i) - 'a']++;
        }

        int l = 0, r = 0;
        // curCount: 当前窗口中包含的s1元素个数
        int targetCount = s1.length(), curCount = 0;
        for (r = 0; r < s1.length(); r++) {
            amount[s2.charAt(r) - 'a']--; 
            if (amount[s2.charAt(r) - 'a'] >= 0) {
                curCount++;
            }
        }
        // 当当前窗口包含s1个数和s1长度相同时,意味着s1所有的元素都出现在了窗口中.
        if (curCount == targetCount) {
            return true;
        }

        while (r < s2.length()) {
            // tick the left out
            // 如果要被移除的l被计入了curCount, 要先把窗口中包含s1元素的个数-1
            if (amount[s2.charAt(l) - 'a'] >= 0) {
                curCount--;
            }
            // 再把取出的还回去
            amount[s2.charAt(l) - 'a']++;
            l++;
            // feed the new member
            // 从amount取出, 表示放入了窗口
            amount[s2.charAt(r) - 'a']--;
            // 看放入窗口后是否多余.
            if (amount[s2.charAt(r) - 'a'] >= 0) {
                curCount++;
            }
            r++;
            if (curCount == targetCount) {
                return true;
            }
        }

        return false;
    }

}

Analysis

时间复杂度O(n), 空间O(1).