算法滑动窗口

滑动窗口算法可以用以解决数组/字符串的子元素问题，它可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。

简而言之，滑动窗口算法在一个特定大小的字符串或数组上进行操作，而不在整个字符串和数组上操作，这样就降低了问题的复杂度，从而也达到降低了循环的嵌套深度。

可以用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。由于区间连续，因此当区间发生变化时，可以通过旧有的计算结果对搜索空间进行剪枝，这样便减少了重复计算，降低了时间复杂度。往往类似于“ 请找到满足 xx 的最 x 的区间（子串、子数组）的 xx ”这类问题都可以使用该方法进行解决。

转载labuladong：

适用题型：

遇到子串问题，首先想到用滑动窗口技巧。(意味着一个串长度一定小与另一个串)

题型分为窗口大小不断变化和窗口大小固定两种题型。

窗口大小变化

思路：

滑动窗口算法的思路是这样：

1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。

2、我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。

4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

这个思路其实也不难，**第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。**左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

上述过程可以简单地写出如下伪码框架：
string s, t;
// 在 s 中寻找 t 的「最小覆盖子串」
int left = 0, right = 0;
string res = s;

while(right < s.size()) {
    window.add(s[right]);
    right++;
    // 如果符合要求，移动 left 缩小窗口
    while (window 符合要求) {
        // 如果这个窗口的子串更短，则更新 res
        res = minLen(res, window);
        window.remove(s[left]);
        left++;
    }
}
return res;

注：

1，输入两个字符串的，需要needs和window两个hash计数器。输入为一个字符串的只需要一个window计数器。

2，shrink条件，即更新结果条件两个地方要注意。

可以用两个哈希表当作计数器解决。用一个哈希表 needs 记录字符串 t 中包含的字符及出现次数，用另一个哈希表 window 记录当前「窗口」中包含的字符及出现的次数，如果 window 包含所有 needs 中的键，且这些键对应的值都大于等于 needs 中的值，那么就可以知道当前「窗口」符合要求了，可以开始移动 left 指针了。

思路：

(1) 往右滑，更新使window符合条件的变量(这里是match)： 当right所处位置字符在needs中，且window中c1出现次数等于needs中c1出现次数时才增加mach。而window中可以记录[left, right]中所有字符，也可以只记录[left, right]范围内只出现在needs中的字符

(2) 窗口内字符满足条件：匹配到的数量等于needs.size()

(3) 结果更新：用start和minLen记录所要求的s的子串起始pos和长度。

(4) 往左滑，更新使window不符合条件的变量(这里是match)

window滑动的过程中只记录s在[left, right]段中在needs中出现过的字符：

string minWindow(string s, string t) {
    // 记录最短子串的开始位置和长度
    int start = 0, minLen = INT_MAX;
    int left = 0, right = 0;
    
    unordered_map<char, int> window;
    unordered_map<char, int> needs;
    for (char c : t) needs[c]++;
    
    int match = 0;
    
    while (right < s.size()) {
        char c1 = s[right];
        if (needs.count(c1)) {
            window[c1]++;
            if (window[c1] == needs[c1]) 
                match++;
        }
        right++;
        
        while (match == needs.size()) {
            if (right - left < minLen) {
                // 更新最小子串的位置和长度
                start = left;
                minLen = right - left;
            }
            char c2 = s[left];
            if (needs.count(c2)) {
                window[c2]--;
                if (window[c2] < needs[c2])
                    match--;
            }
            left++;
        }
    }
    return minLen == INT_MAX ?
                "" : s.substr(start, minLen);
}

window滑动的过程中会记录s在[left, right]段的所有字符：

class Solution {
public:
    string minWindow(string s, string t) {
        int left = 0;
        int right = 0;
        unordered_map<char, int> needs;
        unordered_map<char, int> window;
        for (auto ch : t) {
            needs[ch]++;
        }

        int match = 0;
        int minLen = INT_MAX;
        int start = 0;
        while (right < s.size()) {
            char c1 = s[right];
            window[c1]++;
            if (needs.count(c1) > 0 && (window[c1] == needs[c1])) {
                match++;
            }
            right++; // 扩大窗口右边界

            while (match == needs.size()) { // 扩大窗口右边界后找到一个解。
                                            // 缩减窗口左边界优化这个解
                //更新
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }
                char c2 = s[left];
                if (needs.count(c2) > 0 && (window[c2] == needs[c2])) {
                    match--;
                }
                window[c2]--;
                left++;
            }
        }
        string res = minLen != INT_MAX ? s.substr(start, minLen) : "";
        return res;
    }
};

二、找到字符串中所有字母异位词

思路：

(1) 往右滑，更新使window符合条件的变量(这里是match)： 当right所处位置字符在needs中，且window中c1出现次数等于needs中c1出现次数时才增加mach。window只记录[left, right]范围内只出现在needs中的字符。

(2) 窗口内字符满足条件：匹配到的数量等于needs.size()

(3) 结果更新：只有right - left大小等于p串长度，才是目标子串。

(4) 往左滑，更新使window不符合条件的变量(这里是match)

vector<int> findAnagrams(string s, string t) {
    // 用数组记录答案
    vector<int> res;
    int left = 0, right = 0;
    unordered_map<char, int> needs;
    unordered_map<char, int> window;
    for (char c : t) needs[c]++;
    int match = 0;
    
    while (right < s.size()) {
        char c1 = s[right];
        if (needs.count(c1)) {
            window[c1]++;
            if (window[c1] == needs[c1])
                match++;
        }
        right++;

        while (match == needs.size()) {
            // 如果 window 的大小合适
            // 就把起始索引 left 加入结果
            if (right - left == t.size()) {
                res.push_back(left);
            }
            char c2 = s[left];
            if (needs.count(c2)) {
                window[c2]--;
                if (window[c2] < needs[c2])
                    match--;
            }
            left++;
        }
    }
    return res;
}

三、无重复字符的最长子串

类似之前的思路，使用 window 作为计数器记录窗口中的字符出现次数，然后先向右移动 right，当 window 中出现重复字符时，开始移动 left 缩小窗口，如此往复：

需要注意的是，因为我们要求的是最长子串，所以需要在每次移动 right 增大窗口时更新 res，而不是像之前的题目在移动 left 缩小窗口时更新 res。

// 滑动窗口, 窗口[left, right)和window_map的间接关系,
// window_map中存的就是[left, right)中的元素。
// 增加求子串本身
int lengthOfLongestSubstring(string s) {
    int res = 0;
    int left = 0;
    int right = 0;
    int start = 0;

    // unordered_map<char, int> need;
    unordered_map<char, int> window;
    
    while (right < s.size()) {
        char c1 = s[right];
        window[c1]++;
        right++;

        // 满足条件时：窗口中有重复字符(但不知道此时重复字符ch1处在当前窗口的哪个位置)，
        // 缩小窗口, 直到窗口中与ch1重复的字符被从窗口里拿掉
        while (window[c1] > 1) {
            char c2 = s[left];
            window[c2]--;
            left++;
        }
        // 此时window已经滤掉了重复元素
        // res = max(res, right - left);
        if (right - left > res) {
            res = right - left;
            start = left;
        }
    }
    string resStr = s.substr(start, res);
    return res;
}

// 方法：滑动窗口

// 思路：

// 右边界先移动找到一个满足题意的可以替换 k 个字符以后，所有字符都变成一样的当前看来最长的子串，直到右边界纳入一个字符以后，不能满足的时候停下；然后考虑左边界向右移动，左边界只须要向右移动一格以后，右边界就又可以开始向右移动了，继续尝试找到更长的目标子串； 替换后的最长重复子串就产生在右边界、左边界交替向右移动的过程中。

class Solution1 {
public:
    int characterReplacement(string s, int k) {
        int res = 0;
        int left = 0;
        int right = 0;
        vector<int> window(26);
        int maxCnt = 0;
        // [left, right) 内最多替换 k 个字符可以得到只有一种字符的子串
        while (right < s.size()) {
            window[s[right] - A]++;
            // 在这里维护 maxCount，因为每一次右边界读入一个字符，字符频数增加，才会使得 maxCount 增加
            maxCnt = max(maxCnt, window[s[right] - A]);
            right++;
            if (right - left > maxCnt + k) { // if判断，仅缩小一次窗口左边界
              	// 说明此时 k 不够用(把其它不是最多出现的字符替换以后，都不能填满这个滑动的窗口)，这个时候须要考虑左边界向右移动
                // 移出滑动窗口的时候，频数数组须要相应地做减法
                window[s[left] - A]--;
                left++;
            }
            res = max(res, right - left); // 因为已经缩小了窗口左边界, 因此在这里更新结果
        }
        return res;
    }
};

窗口大小固定

思路：固定长度窗口向前滑动，窗口维护一个total值，每次移动窗口，只需要对窗口加新头、去旧尾两步操作(不要每次滑动都重新把窗口内的值全部计算一遍，这样时间复杂度是O(n*k))保证O(n)时间复杂度。

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        size_t itBound = arr.size() - k;
        int sum = accumulate(arr.begin(), arr.begin() + k, 0);
        int kThreshold = k * threshold;
        int result = sum >= kThreshold ? 1 : 0;
        int headKMinusOneSum = sum - arr[0];
        for (size_t i = 1; i <= itBound; i++) {
            sum = headKMinusOneSum + arr[i + k - 1];
            result = sum >= kThreshold ? result + 1 : result;
            headKMinusOneSum = sum - arr[i];
        }
        return result;
    }
};

class Solution {
public:
    // 穷举, 超时 O(m! * (n-m))
    bool checkInclusion1(string s1, string s2) {
        if (s1.size() > s2.size()) {
            return false;
        }
        sort(s1.begin(), s1.end());
        do {
            if (s2.find(s1) != string::npos) {
                return true;
            }
        } while (next_permutation(s1.begin(), s1.end()));
        return false;
    }
    // 滑动窗口(固定大小子串)，排序
    // 思路：对s1排序，然后一遍遍历s2，每步截取s1.size()长度子串并对子串排序，然后再和
    //      序后的s1比较相等。
    //代码：略
    
    // 滑动窗口(哈希数组), 通过7% + 6%, O(26*m*(n-m))
    // 思路：一遍遍历s2，截取s1.size()长度子串后放入哈希数组2，然后再比较两个哈希数组。
    bool checkInclusion2(string s1, string s2) {
        if (s1.size() > s2.size()) {
            return false;
        }
        vector<int> hashVec1(26);
        size_t s1Len = s1.size();
        for (size_t i = 0; i < s1Len; i++) {
            hashVec1[s1[i] - a]++;
        }
        size_t s2Bound = s2.size() - s1.size() + 1;
        for (size_t i = 0; i < s2Bound; i++) {
            string subS2 = s2.substr(i, s1Len);
            vector<int> hashVec2(26);
            for (size_t j = 0; j < s1Len; j++) {
                hashVec2[subS2[j] - a]++;
            }
            size_t k = 0;
            for (; k < 26; k++) {
                if (hashVec1[k] != hashVec2[k]) {
                    break;
                }
            }
            if (k == 26) {
                return true;
            }
        }
        return false;
    }
    // 子串问题:滑动窗口(哈希窗口)  89.3%, 96.29% O(26*(n - m))
    // 思路：只维护两个哈希数组，一遍遍历s2，比较两个哈希数组。
    bool checkInclusion(string s1, string s2) {
        if (s1.size() > s2.size()) {
            return false;
        }

        vector<int> needs(26);
        vector<int> window(26);
        for (size_t i = 0; i < s1.size(); i++) {
            needs[s1[i] - a]++;
            window[s2[i] - a]++;
        }

        size_t s2Bound = s2.size() - s1.size() + 1;
        for (size_t i = 0; i < s2Bound; i++) {
            size_t k = 0;
            for (; k < 26; k++) {
                if (needs[k] != window[k]) {
                    break;
                }
            }
            if (k == 26) {
                return true;
            }
            if (i == s2Bound - 1) {
                break;
            }
            // 窗口只需加头，去尾两步操作
            window[s2[i + s1.size()] - a]++;
            window[s2[i] - a]--;
        }
        return false;
    }

    // 同上文lc438找到字符串中所有字母异位词: 41ms, 41.5%。用这种解法
    bool checkInclusion(string s, string t) {
        if (s.size() > t.size()) {
            return false;
        }
        int left = 0;
        int right = 0;
        unordered_map<char, int> needs;
        unordered_map<char, int> window;
        for (auto ch : s) {
            needs[ch]++;
        }

        int match = 0;
        while (right < t.size()) {
            char c1 = t[right];
            if (needs.count(c1) != 0) {
                window[c1]++;
                if (window[c1] == needs[c1]) {
                    match++;
                }
            }
            right++;

            while (match == needs.size()) {
                if (right - left == s.size()) {
                    return true;
                }
                char c2 = t[left];
                if (needs.count(c2) != 0) {
                    window[c2]--;
                    if (window[c2] < needs[c2]) {
                        match--;
                    }
                }
                left++;
            }
        }
        return false;
    }
};

思路：// 贪心 + 滑动窗口 + 二叉搜索树中序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // 贪心 + 滑动窗口 + 二叉树中序遍历
    int minDiffInBST(TreeNode* root) {
        vector<int> inOrderPath;
        InOrderTravel(root, inOrderPath);
        int result = INT_MAX;
        // 窗口大小为2, 相邻两元素
        int windowLeft = inOrderPath[0];
        for (size_t i = 1; i < inOrderPath.size(); i++) {
            result = min(result, inOrderPath[i] - windowLeft);
            windowLeft = inOrderPath[i];
        }
        return result;
    }

    void InOrderTravel(TreeNode* root, vector<int>& inOrderPath) {
        if (root != nullptr) {
            InOrderTravel(root->left, inOrderPath);
            inOrderPath.push_back(root->val);
            InOrderTravel(root->right, inOrderPath);
        }
    }
};

滑动窗口题目:

done

done

159. 至多包含两个不同字符的最长子串

done

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int sum = 0;
        int left = 0;
        int right = 0;
        int result = nums.size();
        while (right < nums.size()) {
            sum += nums[right];
            right++;
            while (sum >= s) {
                result = min(result, right - left);
                sum -= nums[left];
                left++;
            }
        }

        return result;
    }
};

方法2：前缀和 + 二分

因为这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正，这里就不能使用二分来查找这个位置了。

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int ans = INT_MAX;
        vector<int> sums(n + 1, 0); 
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            auto bound = lower_bound(sums.begin(), sums.end(), target);
            if (bound != sums.end()) {
                ans = min(ans, static_cast<int>((bound - sums.begin()) - (i - 1)));
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

done 滑动窗口 + 单调队列(单调递减队列)

// 滑动窗口 + 单调队列， 固定窗口大小

// 思路：

// 单调递减队列中存储数组下标, 下标是递增的， 下标对应的值是递减的

// 窗口滑动时，当前元素若大于(或大于等于)队尾下标对应的值则循环出队尾， 若当前队首下标在窗口外(队首下标小于left=i-k)则循环队首出队--保证队列中的值始终是滑动中窗口内的值

注：此类题不能用优先队列代替单调队列，因为无法实现优先队列中的值始终是窗口内的值，不能实现窗口外的值及时出优先队列，eg：[9,10,9,-7,-4,-8,2,-6]，k=5。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if (nums.size() * k == 0) {
            return {};
        }
        vector<int> res;
        deque<int> q;
        for (size_t i = 0; i < k; i++) {
            while (!q.empty() && nums[q.back()] < nums[i]) {
                q.pop_back();
            }
            q.push_back(i);
        }
        res.push_back(nums[q.front()]);
        for (size_t i = k; i < nums.size(); i++) {
            // 队列头是上一步窗口内最大值的索引值。若队列头不在当前窗口内，则队首出队，看第二大的数处于队首，再继续比较
            while (!q.empty() && q.front() <= i - k) {
                q.pop_front();
            }
            while (!q.empty() && nums[q.back()] < nums[i]) {
                q.pop_back();
            }
            q.push_back(i);
            res.push_back(nums[q.front()]);
        }
        return res;
    }
};

done

class Solution {
public:
    // 穷举, 超时 O(m! * (n-m))
    bool checkInclusion1(string s1, string s2) {
        if (s1.size() > s2.size()) {
            return false;
        }
        sort(s1.begin(), s1.end());
        do {
            if (s2.find(s1) != string::npos) {
                return true;
            }
        } while (next_permutation(s1.begin(), s1.end()));
        return false;
    }
    // 滑动窗口(固定大小子串)，排序
    // 思路：对s1排序，然后一遍遍历s2，每步截取s1.size()长度子串并对子串排序，然后再和
    //      序后的s1比较相等。
    //代码：略
    
    // 滑动窗口(哈希数组), 通过7% + 6%, O(26*m*(n-m))
    // 思路：一遍遍历s2，截取s1.size()长度子串后放入哈希数组2，然后再比较两个哈希数组。
    bool checkInclusion2(string s1, string s2) {
        if (s1.size() > s2.size()) {
            return false;
        }
        vector<int> hashVec1(26);
        size_t s1Len = s1.size();
        for (size_t i = 0; i < s1Len; i++) {
            hashVec1[s1[i] - a]++;
        }
        size_t s2Bound = s2.size() - s1.size() + 1;
        for (size_t i = 0; i < s2Bound; i++) {
            string subS2 = s2.substr(i, s1Len);
            vector<int> hashVec2(26);
            for (size_t j = 0; j < s1Len; j++) {
                hashVec2[subS2[j] - a]++;
            }
            size_t k = 0;
            for (; k < 26; k++) {
                if (hashVec1[k] != hashVec2[k]) {
                    break;
                }
            }
            if (k == 26) {
                return true;
            }
        }
        return false;
    }
    // 子串问题:滑动窗口(哈希窗口)  89.3%, 96.29% O(26*(n - m))
    // 思路：只维护两个哈希数组，一遍遍历s2，比较两个哈希数组。
    bool checkInclusion(string s1, string s2) {
        if (s1.size() > s2.size()) {
            return false;
        }
 
        vector<int> needs(26);
        vector<int> window(26);
        for (size_t i = 0; i < s1.size(); i++) {
            needs[s1[i] - a]++;
            window[s2[i] - a]++;
        }
 
        size_t s2Bound = s2.size() - s1.size() + 1;
        for (size_t i = 0; i < s2Bound; i++) {
            size_t k = 0;
            for (; k < 26; k++) {
                if (needs[k] != window[k]) {
                    break;
                }
            }
            if (k == 26) {
                return true;
            }
            if (i == s2Bound - 1) {
                break;
            }
            // 窗口只需加头，去尾两步操作
            window[s2[i + s1.size()] - a]++;
            window[s2[i] - a]--;
        }
        return false;
    }
// 同上文lc438找到字符串中所有字母异位词: 41ms, 41.5%。用这种解法
    bool checkInclusion3(string s, string t) {
        if (s.size() > t.size()) {
            return false;
        }
        int left = 0;
        int right = 0;
        unordered_map<char, int> needs;
        unordered_map<char, int> window;
        for (auto ch : s) {
            needs[ch]++;
        }
 
        int match = 0;
        while (right < t.size()) {
            char c1 = t[right];
            if (needs.count(c1) != 0) {
                window[c1]++;
                if (window[c1] == needs[c1]) {
                    match++;
                }
            }
            right++;
 
            while (match == needs.size()) {
                if (right - left == s.size()) {
                    return true;
                }
                char c2 = t[left];
                if (needs.count(c2) != 0) {
                    window[c2]--;
                    if (window[c2] < needs[c2]) {
                        match--;
                    }
                }
                left++;
            }
        }
        return false;
    }
};

632. 最小区间

727. 最小窗口子序列

其他子串问题：

回文子串

回文子串不用滑动窗口，用中心扩展法。

注：回文串有两种：

(1) "aabaa" (2) "aabba"

class Solution {
public:
    string longestPalindrome(string s)
    {
        int sLength = s.size();
        if (sLength == 0) {
            return "";
        }

        int start = 0;
        int end = 0;
        int maxLen = 0;
        int len = 0;
        string result;
        for (int i = 0; i < sLength; i++) {
            int len1 = CenterExpandValid(s, sLength, i, i); // 尝试计算aabaa类型回文串长度
            int len2 = CenterExpandValid(s, sLength, i, i + 1); // 尝试计算aabbaa类型回文长度串
            len = max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        result = s.substr(start, maxLen);
        return result;
    }
    int  CenterExpandValid(string& s, int sLength, int left, int right)
    {
        while (left >= 0 && right < sLength && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
};