当前位置:   article > 正文

【优选算法】滑动窗口--实现复杂度优化

【优选算法】滑动窗口--实现复杂度优化

目录

209.⻓度最⼩的⼦数组

思路:

代码

3.⽆重复字符的最⻓⼦串

思路

代码:

1004.最⼤连续1的个数III

思路:

代码:

1658.将x减到0的最⼩操作数

思路:正难则反

代码:

904.水果成篮

思路:

代码:


如果想学习滑动窗口,可以试着跟着本篇练习~

l209.⻓度最⼩的⼦数组

给定一个含有 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

思路:

由于此问题分析的对象是「一段连续的区间」,因此可以考虑「滑动窗口」的思想来解决这道题。 让滑动窗口满足:从 i 位置开始,窗口内所有元素的和小于target (那么当窗口内元素之和第一次大于等于目标值的时候,就是 i 位置开始,满足条件的最小长度)。

做法:将右端元素划入窗口中,统计出此时窗口内元素的和

- 如果窗口内元素之和大于等于target :

更新结果,并且将左端元素划出去的同时继续判断是否满足条件并更新结果(因为左端元素可能很小,划出去之后依旧满足条件)

- 如果窗口内元素之和不满足条件:

right++ ,另下一个元素进入窗口。

相信科学(这也是很多题解以及帖子没告诉的事情:只给说怎么做,没给你解释为什么这么做):

为何滑动窗口可以解决问题,并且时间复杂度更低?

  • - 这个窗口寻找的是:以当前窗口最左侧元素(记为 left )为基准,符合条件的情况。也就是在这道题中,从 left1 开始,满足区间和 sum >= target 时的最右侧(记为 right1 )能到哪里。
  • - 我们既然已经找到从 left1 开始的最优的区间,那么就可以大胆舍去 left1 。但是如果继续像方法一一样,重新开始统计第二个元素( left2 )往后的和,势必会有大量重复的计算(因为我们在求第一段区间的时候,已经算出很多元素的和了,这些和是可以在计算下次区间和的时候用上的)。
  • - 此时, right1 的作用就体现出来了,我们只需将 left1 这个值从 sum 中剔除。从 right1 这个元素开始,往后找满足 left2 元素的区间(此时 right1 也有可能是满足的,因为 left1 可能很小。 sum 剔除掉 left1 之后,依旧满足大于等于 target )。这样我们就能省掉大量重复的计算。
  • - 这样我们不仅能解决问题,而且效率也会大大提升。

时间复杂度:虽然代码是两层循环,但是我们的 left 指针和 right 指针都是不回退的,两者最多都往后移动 n 次。因此时间复杂度是 O(N)

sum:

代码

  1. class Solution {
  2. public:
  3. int minSubArrayLen(int target, vector<int>& nums) {
  4. int n=nums.size(),sum=0,len=INT_MAX;
  5. for(int left=0,right=0;right<n;right++)
  6. {
  7. sum+=nums[right];
  8. while(sum>=target)
  9. {
  10. len=min(len,right-left+1);
  11. sum-=nums[left++];
  12. }
  13. }//嵌套判断
  14. return len==INT_MAX?0:len;
  15. }
  16. };

3.⽆重复字符的最⻓⼦串

给定一个字符串 s ,请你找出其中不含有重复字符的 最长 
子串
 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

思路

研究的对象依旧是一段连续的区间,因此继续使用「滑动窗口」思想来优化。

让滑动窗口满足:窗口内所有元素都是不重复的

做法:右端元素 ch 进入窗口的时候,哈希表统计这个字符的频次

  • - 如果这个字符出现的频次超过 1 ,说明窗口内有重复元素,那么就从左侧开始划出窗口,直到 ch 这个元素的频次变为 1 ,然后再更新结果。
  • - 如果没有超过 1 ,说明当前窗口没有重复元素,可以直接更新结果

代码:

  1. class Solution {
  2. public:
  3. int lengthOfLongestSubstring(string s) {
  4. // 存hash
  5. // 使用数组来模拟
  6. int hash[128] = {0}; // 初始化
  7. int n = s.size(), len = 0;
  8. int left = 0, right = 0;
  9. // 进窗口
  10. // 滑动窗口是可以通过增加判断条件,让双重循环,变为单重,里面是条件++
  11. while (right < n) {
  12. // 进窗口
  13. hash[s[right]]++;
  14. // 判断
  15. while (hash[s[right]] > 1)
  16. // 出窗口
  17. hash[s[left++]]--; // 利用循环,直到跳出那个
  18. // 更新结果
  19. len = max(len, right - left + 1);
  20. // 下一个元素进入窗口
  21. right++;
  22. // 滑动窗口,是很少用for的
  23. }
  24. return len;
  25. }
  26. };

1004.最⼤连续1的个数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。

思路:

不要去想怎么翻转,不要把问题想得很复杂,这道题的结果无非就是一段连续的1中间塞了k个0嘛。

因此,我们可以把问题转化成:求数组中一段最长的连续区间,要求这段区间内0的个数不超过k个

既然是连续区间,可以考虑使用「滑动窗口」来解决问题。

算法流程:

a.- 初始化一个大小为2的数组就可以当做哈希表hash了;初始化一些变量left = 0, right = 0, ret = 0;

b.- 当right小于数组大小的时候,一直执行以下循环:

  • - 让当前元素进入窗口,顺便统计到哈希表中;
  • - 检查0的个数是否超标: 如果超标,依次让左侧元素滑出窗口,顺便更新哈希表的值,直到0的个数恢复正常
  • - 程序到这里,说明窗口内元素是符合要求的,更新结果;
  • - right++,处理下一个元素;

c.- 循环结束后,ret 存的就是最终结果。

代码:

  1. class Solution {
  2. public:
  3. int longestOnes(vector<int>& nums, int k) {
  4. int n=nums.size();
  5. int left=0,right=0,len=0,count=0;
  6. //进窗口,直到走到末尾
  7. while(right<n)
  8. {
  9. if(nums[right]==0)
  10. count++;
  11. //判断
  12. while(count>k)
  13. {
  14. //出窗口
  15. if(nums[left]==0)
  16. count--;//先判断这个数的处理,再移动
  17. left++;
  18. }
  19. len=max(len,right-left+1);//每走一步之后就,更新结果
  20. right++;
  21. }
  22. return len;
  23. }
  24. };

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 。

思路:正难则反

题目要求的是数组「左端+右端」两段连续的、和为 x 的最短数组,信息量稍微多一些,不易理清

我们可以转化成求数组内一段连续的、和为 sum(nums) - x 的最长数组。此时,就是熟悉的「滑动窗口」问题了。

常见错误分析:

加上对x过大进行处理就可以啦~思维要缜密 

 

代码:

  1. class Solution {
  2. public:
  3. int minOperations(vector<int>& nums, int x) {
  4. // 正难则反,找出最长的sum-x
  5. int n = nums.size();
  6. int sum = 0, ret =0;
  7. int len = -1, target = 0;//len直接设置为-1
  8. for (int i = 0; i < n; i++)
  9. sum += nums[i];
  10. target = sum - x;
  11. if(target < 0) return -1;//对x过大进行处理,避免之后死循环
  12. for (int left = 0, right = 0; right < n; right++) {
  13. ret += nums[right];
  14. while (ret > target)
  15. ret -= nums[left++];
  16. if (ret == target)
  17. len = max(len, right - left + 1);
  18. }
  19. if(len==-1) return -1;
  20. else return n-len;
  21. }
  22. };

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] 这五棵树。

思路:

右端水果进入窗口的时候,用哈希表统计这个水果的频次。这个水果进来后,判断哈希表的大小:

- 如果大小超过 2:

说明窗口内水果种类超过了两种。那么就从左侧开始依次将水果划出窗口,直到哈希表的大小小于等于 2,然后更新结果

- 如果没有超过 2,

说明当前窗口内水果的种类不超过两种,直接更新结果 ret。

代码:

  1. class Solution {
  2. public:
  3. int totalFruit(vector<int>& fruits) {
  4. int hash[100001] = {0}; // 统计窗⼝内出现了多少种⽔果
  5. int n = fruits.size(), kind = 0,len = 0;
  6. for (int left = 0, right = 0; right < n; right++) {
  7. if (hash[fruits[right]] == 0)
  8. kind++; // 来了一个新种类就++
  9. hash[fruits[right]]++;
  10. if (kind > 2) {
  11. hash[fruits[left]]--;
  12. if (hash[fruits[left]] == 0)
  13. kind--;
  14. left++;//处理完 删掉这个数之后再++
  15. }
  16. // 每次都记录长度
  17. len = max(len, right - left + 1);
  18. }
  19. return len;
  20. }
  21. };
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小惠珠哦/article/detail/762386
推荐阅读
相关标签
  

闽ICP备14008679号