LeetCode 滑动窗口算法进阶解析

相关例题

904. 水果成篮

题目描述

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：

• 1 <= fruits.length <= 10^5
• 0 <= fruits[i] < fruits.length

题目分析

这个题目其实还是一个使用滑动窗口的题目，我们分析题意可以得知我们需要维护的窗口是一个最长的数字类型不大于 2 的窗口，并且题目也说明了这里不会存在不连续的情况（一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘），所以这题可以使用滑动窗口。

实现思路

一开始我们需要定义两个指针都是指向开头的，并且我们这里为了获取数字类型的个数并且出窗口方便，这里需要定义一个哈希表（这里不可以用集合，想想为什么），然后就是窗口的操作了。

我们首先需要将右指针的值入窗口，如果类型数（也就是我们哈希表的大小）大于 2 了，我们就开始出窗口，也就是将我左指针指向的值的哈希值 --，同时减到了 0 还要删除出哈希表（这里就是为什么不能用集合了），出了条件之后就是我们的返回值更新。

最后就是将我们的值返回，其实这里只要数组大小大于了 1 就有返回值。

实现代码

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> h;
        int len = -1;
        int size = fruits.size();
        for (int i = 0, j = 0; j < size; j++) {
            h[fruits[j]]++;
            while (h.size() > 2) {
                h[fruits[i]]--;
                if (h[fruits[i]] == 0) {
                    h.erase(fruits[i]);
                }
                i++;
            }
            len = max(len, j - i + 1);
        }
        return len == -1 ? 0 : len;
    }
};

438. 找到字符串中所有字母异位词

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 10^4
• s 和 p 仅包含小写字母

题目分析

这个题目比较容易陷进找有效开头这个点里面去，其实这个题目不需要我们找有效开头，只需要维护一个满足条件的区间就可以了，所以这个题目还是用的滑动窗口来维持着这样一个区间。

实现思路

我们这里其实就是维持子串的字符哈希值（也就是这个字符出现的个数）要大于等于我们的窗口里面对应字符的哈希值，同时我们的窗口大小也不能大于我们的子串的大小。

首先我们需要预处理我们的子串对应字符的哈希值，同时设置我们需要的一些变量。

然后就是定义两个指针指向开头来遍历我们的父串，如果当前的字符出现次数要小于等于我们的子串对应的字符，我们就将我们的计数 ++，然后就是我们的越界判断，如果我们的长度大于了子串的长度，我们就判断当前父串中左指针的字符出现次数是不是要小于子串对应字符出现的次数，如果是小于等于就将我们的计数 --，这里同时也考虑了我们的非法的情况（非法的字符不参与计数计数 --，但是要和参与的数字一起排除），然后就是判断我们的计数是不是满足题意了并加入到我们的返回数组中，最后就是返回我们的数组了。

实现代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int hash1[26] = {0};
        int hash2[26] = {0};
        for (auto e : p) hash2[e - 'a']++;
        int n = s.size(), m = p.size();
        for (int left = 0, right = 0, count = 0; right < n; right++) {
            if (++hash1[s[right] - 'a'] <= hash2[s[right] - 'a']) count++;
            if (right - left + 1 > m) {
                if (hash1[s[left] - 'a']-- <= hash2[s[left] - 'a']) count--;
                left++;
            }
            if (count == m) ret.push_back(left);
        }
        return ret;
    }
};

串联所有单词的子串

题目描述

给定一个字符串 s 和一个字符串数组 words。words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

• 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。所以我们返回一个空数组。

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示：

• 1 <= s.length <= 10^4
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 和 s 由小写英文字母组成

题目分析

这是一个困难题，但是如果我们有了上面那个题目作为支撑，这个题目的思路还是比较好想的，我们这里其实可以吧每一个单词看成是一个一个的字母，这个问题就变成了求字符串里面所有的字母的异位词，处理对象从字符变成了单词而已，但是这个题目还是有一个比较重要的优化思路需要了解。

实现思路

我们这里首先就是确定我们的开始位置，我们这里不可以直接从 0 开始，这样会出现有的情况没考虑到，同时这里直接设置每个字符都作为一次我们的开头也是不可以的（会有很多重复的结果），这里我们应该只设置前 words 中单词的长度个字符，这样就可以不重不漏，我们这里还是画图理解。

搞定了开头的字符之后，我们接下来的实现就是和之前实现【找到字符串中所有字母异位词】的逻辑一样了，只不过这里有一些细节需要注意，详细细节可以看代码。

代码实现

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        int n = s.size(), len = words[0].size(), m = words.size();
        unordered_map<string, int> hash1;
        for (auto e : words) hash1[e]++;
        for (int i = 0; i < len; i++) {
            unordered_map<string, int> hash2;
            for (int left = i, right = i, count = 0; right + len <= n; right += len) {
                string in = s.substr(right, len);
                if (++hash2[in] <= hash1[in]) count++;
                if (right - left + 1 > len * m) {
                    string out = s.substr(left, len);
                    if (hash2[out]-- <= hash1[out]) count--;
                    left += len;
                }
                if (count == m) ret.push_back(left);
            }
        }
        return ret;
    }
};

最小覆盖子串

题目描述

给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 10^5
• s 和 t 由英文字母组成

**进阶：**你能设计一个在 O(m+n) 时间内解决此问题的算法吗？

题目分析

这个题目是一个困难题，这里使用的还是滑动窗口的知识，我们维护的窗口是一个最小长度并且覆盖了所有目标字符的子串，我们要做的就是维护好这个子串并且实时更新出最小的答案。

实现思路

我们这里首先需要预处理我们需要覆盖串中字符的出现次数，处理好之后我们还需要定义一个长度的最大值，然后就是我们窗口的维护了，这个时候我们需要定义两个指针来指向我们的开头位置，首先将我们的右指针指向的字符出现的次数 ++ 后判断是不是属于我们的目标串，属于就将计数 ++；当我们的计数等于我们目标串的大小时，我们就可以来更新我们的最小长度了和我们的返回串的开头了，与此同时我们需要从左边出窗口并判断是不是影响我们的窗口的条件；最后就是我们的返回值返回了，如果还是最大值说明没有更新，于是返回空串，反之将我们返回串返回。

实现代码

class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.size();
        int k = t.size();
        unordered_map<char, int> h1;
        unordered_map<char, int> h2;
        for (auto& e : t) { h1[e]++; }
        int cnt = 0;
        int start = 0;
        int len = 0x3f3f3f3f;
        for (int l = 0, r = 0; r < n; r++) {
            if (++h2[s[r]] <= h1[s[r]]) cnt++;
            while (cnt == k) {
                if (len > r - l + 1) {
                    len = r - l + 1;
                    start = l;
                }
                if (h2[s[l]]-- == h1[s[l++]]) cnt--;
            }
        }
        if (len == 0x3f3f3f3f) return "";
        else {
            string ret(s.begin() + start, s.begin() + start + len);
            return ret;
        }
    }
};