大图做网站背景加载慢,亚马逊雨林原始部落,福田在线官网,服务器搭建网站算法沉淀——滑动窗口 01.长度最小的子数组02.无重复字符的最长子串03.最大连续1的个数 III04.将 x 减到 0 的最小操作数05.水果成篮06.找到字符串中所有字母异位词07.串联所有单词的子串08.最小覆盖子串 滑动窗口算法是一种用于解决数组或列表中子数组或子序列问题的有效技巧。… 算法沉淀——滑动窗口 01.长度最小的子数组02.无重复字符的最长子串03.最大连续1的个数 III04.将 x 减到 0 的最小操作数05.水果成篮06.找到字符串中所有字母异位词07.串联所有单词的子串08.最小覆盖子串 滑动窗口算法是一种用于解决数组或列表中子数组或子序列问题的有效技巧。它通过维护一个可变大小的窗口通常是一个连续的子数组或子序列在数据流中滑动该窗口来进行问题求解。这种方法在一维数组和二维数组中都有应用并且在字符串处理中也很常见。 滑动窗口算法的基本思想是使用两个指针通常是左指针left和右指针right来定义窗口通过移动这两个指针调整窗口的大小和位置从而在不重复计算的情况下找到问题的解。
以下是滑动窗口算法的一般步骤
初始化窗口 定义左指针和右指针并将窗口初始化为满足问题条件的初始状态。移动窗口 不断移动右指针扩展窗口大小直到不再满足问题条件为止。调整窗口 一旦窗口不再满足问题条件开始移动左指针缩小窗口大小直到满足问题条件为止。记录解 在窗口移动的过程中记录满足问题条件的解。
滑动窗口算法适用于一些问题例如
子数组和子序列的最大/最小值 在数组中找到满足条件的子数组或子序列的最大或最小值。子数组和子序列的和或平均值 在数组中找到满足条件的子数组或子序列的和或平均值。字符串处理问题 如找到最小覆盖子串、找到没有重复字符的最长子串等。
下面我们通过几个真题来学习这个算法
01.长度最小的子数组
题目链接https://leetcode.cn/problems/minimum-size-subarray-sum/
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] 并返回其长度**。**如果不存在符合条件的子数组返回 0 。
示例 1
输入target 7, nums [2,3,1,2,4,3]
输出2
解释子数组 [4,3] 是该条件下的长度最小的子数组。示例 2
输入target 4, nums [1,4,4]
输出1示例 3
输入target 11, nums [1,1,1,1,1,1,1,1]
输出0思路
在最开始没接触这种算法题时我们要先建立滑动窗口的概念首先像这种题目要求是连续的情况下我们就要想到这种算法思想然后滑动窗口主要分为四个步骤进窗口、判断、出窗口、更新结果其中更新结果要根据不同的情况放在不同的位置比如上面这道题
这里使用滑动窗口算法用于找到数组中和大于等于目标值 target 的最短子数组的长度。
初始化 使用两个指针 left 和 right都初始指向数组的起始位置。同时定义变量 sum 用来记录当前窗口中元素的和以及变量 len 用来记录当前找到的最短子数组的长度。窗口扩展 在一个循环中不断将右指针 right 向右移动累加元素的值到 sum 中。如果 sum 大于等于目标值 target说明当前窗口的和满足条件。窗口收缩 进入内层循环将左指针 left 向右移动缩小窗口大小同时更新 len 为当前窗口的长度。然后从 sum 中减去左侧移出窗口的元素的值。循环继续 继续上述步骤直到右指针 right 移动到数组的末尾。在整个过程中不断更新 len 为找到的最短子数组的长度。返回结果 最终返回 len如果没有找到满足条件的子数组返回 0。
代码
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int nnums.size(),sum0,lenINT_MAX;for(int left0,right0;rightn;right){sumnums[right];while(sumtarget){lenmin(len,right-left1);sum-nums[left];}}return lenINT_MAX?0:len;}
};02.无重复字符的最长子串
题目链接https://leetcode.cn/problems/longest-substring-without-repeating-characters/
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。示例 2:
输入: s bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b所以其长度为 1。示例 3:
输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。思路
这里使用暴力枚举的方法是可以通过的但是不推荐这里我们使用滑动窗口来进行遍历再借用一个哈希数组来记录字符出现的频次每个字符最多出现一次如果出现两次那么左边一直向右滑动直到变为1再进行滑动时我们更新最大长度在使用哈希存储时因为这里是字符我们可以使用数组模拟哈希结构这样可以提高效率。
初始化 使用两个指针 left 和 right 分别指向字符串的起始位置并初始化一个长度为 128 的哈希表 hash 用于记录字符出现的次数。同时初始化变量 len 用于记录当前的最长无重复字符子串的长度。窗口扩展 在一个循环中不断将右指针 right 向右移动同时在哈希表中记录字符的出现次数。如果发现当前字符的出现次数大于 1说明出现了重复字符。窗口收缩 进入内层循环将左指针 left 向右移动缩小窗口大小。在这个过程中不断减少哈希表中左指针对应字符的出现次数直到当前窗口中没有重复字符为止。更新最长长度 在每一步中都更新 len 为当前窗口的长度 right - left 1 与已经记录的最大长度的较大者。循环继续 继续上述步骤直到右指针 right 移动到字符串的末尾。返回结果 最终返回 len即最长无重复字符子串的长度。
代码
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128]{0};int ns.size(),len0,left0,right0;while(rightn){hash[s[right]];while(hash[s[right]]1) hash[s[left]]--;len max(len,right-left1);right;}return len;}
};03.最大连续1的个数 III
题目链接https://leetcode.cn/problems/max-consecutive-ones-iii/
给定一个二进制数组 nums 和一个整数 k如果可以翻转最多 k 个 0 则返回 数组中连续 1 的最大个数 。
示例 1
输入nums [1,1,1,0,0,0,1,1,1,1,0], K 2
输出6
解释[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1最长的子数组长度为 6。示例 2
输入nums [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K 3
输出10
解释[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1最长的子数组长度为 10。思路
这里我们首先不要被题目误导题目让我们翻转0我们也不用真的翻转我们可以利用滑动窗口的思想在窗口内最大容纳k个0超过就出窗口直到又是k个0再继续入窗口每次更新最大长度即可。
初始化 使用两个指针 left 和 right 分别指向数组的起始位置并初始化变量 zero 用于记录当前窗口中 0 的个数。同时初始化变量 len 用于记录当前的最大长度。窗口扩展 在一个循环中不断将右指针 right 向右移动。如果当前元素为 0将 zero 增加 1。窗口收缩 进入内层循环如果窗口中的 0 的个数大于 k说明需要缩小窗口将左指针 left 向右移动减少窗口中 0 的个数。在这个过程中如果左指针指向的元素是 0则将 zero 减少 1。更新最大长度 在每一步中都更新 len 为当前窗口的长度 right - left 1 与已经记录的最大长度的较大者。循环继续 继续上述步骤直到右指针 right 移动到数组的末尾。返回结果 最终返回 len即包含最多 k 个 0 的连续子数组的最大长度。
代码
class Solution {
public:int longestOnes(vectorint nums, int k) {int nnums.size(),zero0,len0;for(int left0,right0;rightn;right){if(nums[right]0) zero;while(zerok) if(nums[left]0) zero--;lenmax(len,right-left1);}return len;}
};04.将 x 减到 0 的最小操作数
题目链接https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/
给你一个整数数组 nums 和一个整数 x 。每一次操作时你应当移除数组 nums 最左边或最右边的元素然后从 x 中减去该元素的值。请注意需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 返回 最小操作数 否则返回 -1 。
示例 1
输入nums [1,1,4,2,3], x 5
输出2
解释最佳解决方案是移除后两个元素将 x 减到 0 。示例 2
输入nums [5,6,7,8,9], x 4
输出-1示例 3
输入nums [3,2,20,1,1,3], x 10
输出5
解释最佳解决方案是移除后三个元素和前两个元素总共 5 次操作将 x 减到 0 。思路
首先我们看到这道题可能并不容易想到用滑动窗口来解可能有很多人开始会想到双指针但是那样要处理的细节太多不容易通过其实这里我们可以将问题转化从左右两边减去最少的操作数来达到要求我们可以转换成将数组总和减去X在中间找到最长的子数组之和等于这个数再将原数组长度与子数组长度相减便可以求出最小操作数这样是不是就更简单了呢
计算总和 遍历数组计算数组中所有元素的和并保存在变量 sum 中。计算目标差值 计算目标差值 t即 t sum - x。滑动窗口求解 使用滑动窗口的思想在一个循环中不断将右指针 right 向右移动累加元素的值到 tmp 中。同时在内层循环中如果 tmp 大于目标差值 t将左指针 left 向右移动减少窗口的和。在每一步中检查当前窗口的和是否等于目标差值 t。更新最大窗口长度 在每一步中如果当前窗口的和等于目标差值 t则更新 ret 为当前窗口的长度 right - left 1 和已经记录的最大长度的较大者。计算结果 最终返回操作数即数组长度减去最大窗口长度。如果 ret 仍然为初始值 -1则说明无法找到符合条件的子数组返回 -1。
代码
class Solution {
public:int minOperations(vectorint nums, int x) {int nnums.size(),sum0,ret-1;for(const auto num : nums) sumnum;int tsum-x;if(t0) return -1;for(int left0,right0,tmp0;rightn;right){tmpnums[right];while(tmpt) tmp-nums[left];if(tmpt) retmax(ret,right-left1);}if(ret-1) return -1;else return n-ret;}
};05.水果成篮
题目链接https://leetcode.cn/problems/fruit-into-baskets/
你正在探访一家农场农场从左到右种植了一排果树。这些树用一个整数数组 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] 这五棵树。思路
首先我们这里同样可以采取滑动窗口的方式进出窗口同时更新最大长度即可这里需要借助哈希容器来记录水果的种类当然我们也可以直接用数组来模拟哈希这样可以提高效率这里题目告诉我们最大长度是10^5因此我们可以建立一个100001大小的数组来模拟哈希。
初始化 使用两个指针 left 和 right 分别指向数组的起始位置并初始化一个数组 hash 用于记录水果的出现次数。同时初始化变量 ret 用于记录最大长度以及变量 kind 用于记录当前窗口中不同水果的种类数。滑动窗口求解 在一个循环中不断将右指针 right 向右移动。如果当前水果是一种新的水果即 hash[fruits[right]] 0则将 kind 增加 1。在哈希表中记录当前水果的出现次数。窗口收缩 如果当前窗口中不同水果的种类数 kind 大于 2说明窗口中包含了超过两种不同水果。进入内层循环将左指针 left 向右移动减小窗口的大小。在这个过程中不断减少哈希表中左指针指向的水果的出现次数并更新 kind。更新最大长度 在每一步中都更新 ret 为当前窗口的长度 right - left 1 与已经记录的最大长度的较大者。循环继续 继续上述步骤直到右指针 right 移动到数组的末尾。返回结果 最终返回 ret即包含最多两种不同水果的连续子数组的最大长度。
代码
class Solution {
public:int totalFruit(vectorint fruits) {int hash[100001]{0};int ret0,kind0,nfruits.size();for(int left0,right0;rightn;right){if(hash[fruits[right]]0) kind;hash[fruits[right]];if(kind2){hash[fruits[left]]--;if(hash[fruits[left]]0) kind--;left;}retmax(ret,right-left1);}return ret;}
};06.找到字符串中所有字母异位词
题目链接https://leetcode.cn/problems/find-all-anagrams-in-a-string/
给定两个字符串 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 的异位词。思路
这里我们可以借助两个哈希表先存储p字符串的各字母个数再使用另一个哈希表进行长度为p字符串长度的固定滑动窗口对s字符串进行遍历合法字符进窗口计数合法字符出窗口计数–只有计数与p字符串长度相等时存储窗口左下标最后返回存储数组
代码
class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint ret;int hash1[26]{0};int hash2[26]{0};for(const auto c:p) hash1[c-a];int ns.size(),mp.size(),count0;for(int left0,right0;rightn;right){char c1s[right];if(hash2[c1-a]hash1[c1-a]) count;if(right-left1m){char c2s[left];if(hash2[c2-a]--hash1[c2-a]) count--;}if(countm) ret.push_back(left);}return ret;}
};07.串联所有单词的子串
题目链接https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如如果 words [ab,cd,ef] 那么 abcdef abefcdcdabef cdefabefabcd 和 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] 顺序排列的连接。思路
其实这里问题和上面的问题相同只不过将字符变成了字符串根据题目条件每个组合字符串都是相等长度所以我们的计数条件也可以比较明确就是一个字串的长度与所有子串之积而且我们要保证不能有遗漏的情况所以我们要从不同的起始点开始遍历单个字串长度次还需要注意的一点就是这里是字符串所以我们不能使用数组来模拟哈希这里就需使用容器其它的和上面的算法并无二异都是使用滑动窗口的方式。
初始化 使用一个哈希表 hash1 记录单词列表 words 中每个单词的出现次数。遍历起始位置 对于每个可能的起始位置 i其中 i 的范围是 [0, len - 1]其中 len 是单词长度。这是为了确保能够覆盖到所有可能的子串。滑动窗口求解 在一个循环中不断将右指针 right 向右移动每次移动一个单词的长度 len。在每一步中截取字符串 str1表示当前窗口的单词。然后更新哈希表 hash2表示当前窗口内各单词的出现次数。检查匹配 在每一步中检查截取的字符串 str1 是否在哈希表 hash1 中出现并且当前窗口内该单词的出现次数不超过 hash1 中的次数。如果是则将 count 增加 1。这里和下面的count–先检查是一个提升效率的方式不写也不影响代码运行主要原因是如果hash1中没有这个键它就会直接插入这对性能的消耗可能很大。窗口收缩 如果当前窗口的长度超过了需要的总长度 len * m则需要收缩窗口。将左指针 left 向右移动每次移动一个单词的长度 len。在每一步中截取字符串 str2表示当前窗口收缩的单词。然后检查截取的字符串 str2 是否在哈希表 hash1 中出现并且当前窗口内该单词的出现次数不超过 hash1 中的次数。如果是则将 count 减少 1。更新结果 在每一步中如果 count 等于单词列表 words 的长度 m说明当前窗口中包含了所有的单词将左指针的位置加入结果数组 ret。循环继续 继续上述步骤直到右指针 right 移动到字符串 s 的末尾。返回结果 最终返回结果数组 ret。
代码
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {vectorint ret;unordered_mapstring,int hash1;for(const auto str:words) hash1[str];int ns.size(),mwords.size(),lenwords[0].size();for(int i0;ilen;i){unordered_mapstring,int hash2;for(int lefti,righti,count0;rightlenn;rightlen){string str1s.substr(right,len);hash2[str1];;if(hash1.count(str1)hash2[str1]hash1[str1]) count;if(right-left1len*m){string str2s.substr(left,len);if(hash1.count(str2)hash2[str2]hash1[str2]) count--;hash2[str2]--;leftlen;}if(countm) ret.push_back(left);}}return ret;}
};08.最小覆盖子串
题目链接https://leetcode.cn/problems/minimum-window-substring/
给你一个字符串 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 的子串中
因此没有符合条件的子字符串返回空字符串。思路
这里和前面两题类似还是使用滑动窗口加哈希的方式来解决只不过这里可以有重复字符因此我们在计数时只要有一个就不再计数出窗口也一样当计数和记录的种类相同时我们更新起始位置和最小长度最后返回字串即可。
初始化 使用两个数组 hash1 和 hash2 分别记录字符串 t 中字符的出现次数和当前窗口中字符的出现次数。同时使用变量 kind 记录不同字符的种类数。统计字符串 t 中字符次数 遍历字符串 t更新数组 hash1 中对应字符的出现次数并更新 kind。滑动窗口求解 在一个循环中不断将右指针 right 向右移动。在每一步中截取字符串 c1 表示当前窗口的右端字符。然后更新数组 hash2 中右指针指向字符的出现次数并根据当前窗口中字符的出现次数与字符串 t 中相应字符的出现次数比较更新 count。检查匹配 在每一步中如果 count 等于 kind说明当前窗口中包含了字符串 t 中的所有字符。进入内层循环更新最小窗口的长度和起始位置。将左指针 left 向右移动减小窗口的大小。在这个过程中不断减少数组 hash2 中左指针指向字符的出现次数并根据当前窗口中字符的出现次数与字符串 t 中相应字符的出现次数比较更新 count。更新结果 在每一步中如果找到更小的窗口则更新 minl 和 begin。循环继续 继续上述步骤直到右指针 right 移动到字符串 s 的末尾。返回结果 最终返回最小窗口子串如果没有找到则返回空字符串。
代码
class Solution {
public:string minWindow(string s, string t) {int hash1[128]{0};int hash2[128]{0};int kind0;for(const auto ch:t) if(hash1[ch]0) kind;int begin-1,minlINT_MAX,ns.size();for(int left0,right0,count0;rightn;right){char c1s[right];if(hash2[c1]hash1[c1]) count;while(countkind){if(right-left1minl){minlright-left1;beginleft;}char c2s[left];if(hash2[c2]--hash1[c2]) count--;}}if(begin-1) return ;return s.substr(begin,minl);}
};
