【算法专题】滑动窗口_网站优化分享

您的位置：上海毫米网络优化公司 > 网站优化分享 >

滑动窗口

滑动窗口
- 1. 长度最小的子数组
- 2. 无重复字符的最长子串
- 3. 最大连续1的个数Ⅲ
- 4. 将 x 减到 0 的最小操作数
- 5. 水果成篮
- 6. 找到字符串中所有字母异位词
- 7. 串联所有单词的子串
- 8. 最小覆盖子串
  滑动窗口
  
  1. 长度最小的子数组
  
  题目链接 -> Leetcode -209.长度最小的子数组
  
  Leetcode -209.长度最小的子数组
  
  题目：给定一个含有 n 个正整数的数组和一个正整数 target 。
  
  找出该数组中满足其和 ≥ target 的长度最小的连续子数组[numsl, numsl + 1, …, 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
  
  提示：
  1 <= target <= 10^9
  1 <= nums.length <= 10^5
  1 <= nums[i] <= 10^5
  
  思路：由于此问题分析的对象是「⼀段连续的区间」，因此可以考虑「滑动窗口」的思想来解决这道题。让滑动窗口满足：从 i 位置开始，窗口内所有元素的和小于 target （那么当窗口内元素之和第一次大于等于目标值的时候，就是 i 位置开始，满足条件的最小长度）。
  做法：将右端元素划入窗口中，统计出此时窗口内元素的和：
  ▪ 如果窗口内元素之和大于等于 target ：更新结果，并且将左端元素划出去的同时继续判断是否满足条件并更新结果（因为左端元素可能很小，划出去之后依旧满足条件）
  ▪ 如果窗口内元素之和不满足条件： right++ ，另下⼀个元素进⼊窗口。
  
  代码如下：
```
		class Solution {
		public:
		    int minSubArrayLen(int target, vector& nums) 
		    {
		        int left = 0,right = 0,sum = 0,ans = INT_MAX;
		        while(right < nums.size())
		        {
		            // 进窗口
		            sum += nums[right];
		
		            // 满足条件就更新结果
		            while(sum >= target)
		            {
		                ans = min(ans, right - left + 1);
		
		                // 出窗口
		                sum -= nums[left];
		                left++;
		            }
		            right++;
		        }
		        return ans == INT_MAX? 0 : ans;
		    }
		};
```
  为何滑动窗口可以解决问题，并且时间复杂度更低？
  - 这个窗口寻找的是：以当前窗口最左侧元素（记为 left1 ）为基准，符合条件的情况。也就是在这道题中，从 left1 开始，满足区间和 sum >= target 时的最右侧（记为right1 ）能到哪里。
  - 我们既然已经找到从 left1 开始的最优的区间，那么就可以大胆舍去 left1 。但是如果继续像暴力解法，重新开始统计第二个元素（ left2 ）往后的和，势必会有大量重复的计算（因为我们在求第一段区间的时候，已经算出很多元素的和了，这些和是可以在计算下次区间和的时候用上的）。
  - 此时， rigth1 的作用就体现出来了，我们只需将 left1 这个值从 sum 中剔除。从 right1 这个元素开始，往后找满足 left2 元素的区间（此时 right1 也有可能是满足的，因为 left1 可能很小。 sum 剔除掉 left1 之后，依旧满足大于等于 target ）。这样我们就能省掉大量重复的计算。这样我们不仅能解决问题，而且效率也会大大提升。
  - 时间复杂度：虽然代码是两层循环，但是我们的 left 指针和 right 指针都是不回退的，两者最多都往后移动 n 次。因此时间复杂度是 O(N).
    2. 无重复字符的最长子串
    
    题目链接 -> Leetcode -3.无重复字符的最长子串
    
    Leetcode -3.无重复字符的最长子串
    
    题目：给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
    
    示例 1:
    输入: s = “abcabcbb”
    输出 : 3
    解释 : 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
    
    示例 2 :
    输入 : s = “bbbbb”
    输出 : 1
    解释 : 因为无重复字符的最长子串是 “b”，所以其长度为 1。
    
    示例 3 :
    输入 : s = “pwwkew”
    输出 : 3
    解释 : 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
    请注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。
    
    提示：
    0 <= s.length <= 5 * 10^4
    s 由英文字母、数字、符号和空格组成
    
    思路：研究的对象依旧是一段连续的区间，因此继续使用「滑动窗口」思想来优化。让滑动窗口满足：窗口内所有元素都是不重复的。
    做法：右端元素 ch 进⼊窗口的时候，哈希表统计这个字符的频次：
    a. 如果这个字符出现的频次超过 1 ，说明窗口内有重复元素，那么就从左侧开始划出窗口，直到 ch 这个元素的频次变为 1 ，然后再更新结果。
    b. 如果没有超过 1 ，说明当前窗口没有重复元素，可以直接更新结果
    
    代码如下：
```
		class Solution {
		public:
		    int lengthOfLongestSubstring(string s)
		    {
		        if (s.size() == 0) return 0;
		
		        int hash[128] = { 0 };
		
		        int ans = INT_MIN;
		        for (int left = 0, right = 0; right < s.size(); right++)
		        {
		            // 进窗口
		            hash[s[right]]++;
		
		            // 出窗口
		            while (hash[s[right]] > 1)
		            {
		                hash[s[left]]--;
		                left++;
		            }
		
		            // 出窗口后取值
		            ans = max(right - left + 1, ans);
		        }
		        return ans;
		    }
		};
```
    3. 最大连续1的个数Ⅲ
    
    题目链接 -> Leetcode -1004.最大连续1的个数Ⅲ
    
    Leetcode -1004.最大连续1的个数Ⅲ
    
    题目：给定一个二进制数组 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。
    
    提示：
    1 <= nums.length <= 10^5
    nums[i] 不是 0 就是 1
    0 <= k <= nums.length
    
    思路：不用去想怎么翻转，这道题的结果无非就是⼀段连续的 1 中间塞了 k 个 0 ；因此，我们可以把问题转化成：求数组中一段最长的连续区间，要求这段区间内 0 的个数不超过 k 个。
    
    代码如下：
```
		class Solution {
		public:
		    int longestOnes(vector& nums, int k) 
		    {
		        int ans = 0, tmp = k;
		        for(int left = 0,right = 0;right < nums.size();right++)
		        {
		            // 有一个 0 进窗口 k 就减一
		            if(nums[right] == 0 && k >= 0)
		            {
		                k--;
		            }
		            
		            // 窗口内超过 k 个 0，出窗口并更新 k
		            while(nums[right] == 0 && k < 0)
		            {
		                if(nums[left] == 0)
		                    ++k;
		
		                left++;
		            }
		            ans = max(ans, right - left + 1);
		        }
		        return ans;
		    }
		};
```
    4. 将 x 减到 0 的最小操作数
    
    题目链接 -> Leetcode -1658.将 x 减到 0 的最小操作数
    
    Leetcode -1658.将 x 减到 0 的最小操作数
    
    题目：给你一个整数数组 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 。
    
    提示：
    1 <= nums.length <= 10^5
    1 <= nums[i] <= 10^4
    1 <= x <= 10^9
    
    思路：我们可以转化成求数组内一段连续的、和为 sum(nums) - x 的最长数组。此时，就是熟悉的「滑动窗口」问题了。
    
    代码如下：
```
		class Solution {
		public:
		    int minOperations(vector& nums, int x)
		    {
		        int ans = INT_MIN, sum = 0;
		
		        // 转换为求和为 sum(nums)-x 的最长子数组问题
		        for (int i = 0; i < nums.size(); i++) sum += nums[i];
		
		        int target = sum - x, slipSum = 0;
		        if (target < 0) return -1;
		
		        // 操作窗口
		        for (int left = 0, right = 0; right < nums.size(); right++)
		        {
		            // 进窗口
		            slipSum += nums[right];
		
		            // 出窗口
		            while (slipSum > target)
		            {
		                slipSum -= nums[left];
		                left++;
		            }
		
		            // 更新数据
		            if (slipSum == target)
		                ans = max(ans, right - left + 1);
		        }
		
		        return ans == INT_MIN ? -1 : nums.size() - ans;
		    }
		};
```
    5. 水果成篮
    
    题目链接 -> Leetcode -904.水果成篮
    
    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，然后更新结果；
      - 如果没有超过 2，说明当前窗口内水果的种类不超过两种，直接更新结果 ans.
        代码如下：
        
        class Solution { public: int totalFruit(vector& fruits) { int ans = 0; unordered_map hash; for(int left = 0,right = 0;right < fruits.size();right++) { // 进窗口 hash[fruits[right]]++; // 超过两个种类的水果，就出窗口，并更新哈希表 while(hash.size() > 2) { hash[fruits[left]]--; // 如果当前水果种类已经为 0，删除哈希表中这种水果的种类 if(hash[fruits[left]] == 0) hash.erase(fruits[left]); left++; } ans = max(ans, right - left + 1); } return ans; } };
        
        6. 找到字符串中所有字母异位词
        
        题目链接 -> Leetcode -438.找到字符串中所有字母异位词
        
        Leetcode -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 仅包含小写字母
        
        思路：
        
        因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；
        当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p的异位词；
        因此可以用两个大小为 26 的数组来模拟哈希表，一个来保存 s 中的子串每个字符出现的个数，另一个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。
        代码如下：
        
        class Solution { public: vector findAnagrams(string s, string p) { vector ret; int hash1[26] = {0}; for(auto& ch : p) hash1[ch - 'a']++; int len = p.size(); int hash2[26] = {0}; // count 维护s在p中的有效字符个数 int count = 0; for(int left = 0,right = 0;right < s.size();right++) { hash2[s[right] - 'a']++; if(hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) count++; // 出窗口 if(right - left + 1 > len) { char out = s[left]; left++; // 判断出窗口的字符是否是p中的有效字符，如果是则维护 count if(hash2[out - 'a'] <= hash1[out - 'a']) count--; hash2[out - 'a']--; } if(count == len) { ret.push_back(left); } } return ret; } };
        
        7. 串联所有单词的子串
        
        题目链接 -> Leetcode -30.串联所有单词的子串
        
        Leetcode -30.串联所有单词的子串
        
        题目：给定一个字符串 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 由小写英文字母组成
        
        思路：如果我们把每一个单词看成一个一个字母，问题就变成了找到「字符串中所有的字母异位词」。无非就是之前处理的对象是一个一个的字符，我们这里处理的对象是一个一个的单词。
        
        代码如下：
        
        class Solution { public: vector findSubstring(string s, vector& words) { vector ret; // hash1 记录 words 中的字符串 unordered_map hash1; for (const auto& str : words) hash1[str]++; // words 中每个字符串的长度 int strLen = words[0].size(); // 遍历前 strLen 个即可 for (int i = 0; i < strLen; i++) { // hash2 记录组合成的字符串 unordered_map hash2; for (int left = i, right = i, count = 0; right < s.size(); right += strLen) { string in = s.substr(right, strLen); hash2[in]++; // count 维护有效字符串的数量，符合则 ++ if (hash2[in] <= hash1[in]) count++; // 出窗口判断 if (right - left + 1 > strLen * words.size()) { string out = s.substr(left, strLen); if (hash2[out] <= hash1[out]) count--; hash2[out]--; left += strLen; } if (count == words.size()) { ret.push_back(left); } } } return ret; } };
        
        8. 最小覆盖子串
        
        题目链接 -> Leetcode -76.最小覆盖子串
        
        Leetcode -76.最小覆盖子串
        
        题目：给你一个字符串 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 由英文字母组成
        
        思路：研究对象是连续的区间，因此可以尝试使用滑动窗口的思想来解决。
        如何判断当前窗口内的所有字符是符合要求的呢？
        
        我们可以使用两个哈希表，其中一个将目标串的信息统计起来，另一个哈希表动态的维护窗口内字符串的信息。
        当动态哈希表中包含目标串中所有的字符，并且对应的个数都不小于目标串的哈希表中各个字符的个数，那么当前的窗口就是⼀种可行的方案
        代码如下：
        
        class Solution { public: string minWindow(string s, string t) { int hash1[128] = {0}; // kinds 统计 t 中字符类型的数量 int kinds = 0; for(auto& ch : t) if(hash1[ch]++ == 0) kinds++;; int hash2[128] = {0}; int minLen = INT_MAX, begin = -1; for(int left = 0,right = 0,count = 0;right < s.size();right++) { hash2[s[right]]++; // 字符出现的次数必须等于hash1中的次数，窗口维护的有效字符类型才可以统计 if(hash2[s[right]] == hash1[s[right]]) count++; while(count == kinds) { if(right - left + 1 < minLen) { minLen = right - left + 1; begin = left; } char out = s[left]; left++; if(hash2[out] <= hash1[out]) count--; hash2[out]--; } } if(begin == -1) return ""; return s.substr(begin, minLen); } };
        
        seo优化系统建筑公司网站设计免费咨询上海网站制作套餐小程序模板平台腾讯企业网页设计高端网站开发公司

上一篇：第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆优化 or 线性DP？

下一篇：机器学习之逻辑回归(Logit模型）实现—基于R语言（附完整代码）

滑动窗口

滑动窗口

1. 长度最小的子数组

2. 无重复字符的最长子串

3. 最大连续1的个数Ⅲ

4. 将 x 减到 0 的最小操作数

5. 水果成篮

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

7. 串联所有单词的子串

8. 最小覆盖子串