「数组」定长滑动窗口|不定长滑动窗口 / LeetCode 2461|2958(C++)

embedded/2024/12/23 5:07:50/

目录

概述

1.定长滑动窗口

思路

复杂度

Code

2.不定长滑动窗口

思路

复杂度

Code

总结


概述

在双指针合集中,我们介绍了双指针算法

「数组」数组双指针算法合集:二路合并|逆向合并|快慢去重|对撞指针 / LeetCode 88|26|11(C++)

从线性枚举到双指针,我们维护的变量数量从1个提升到2个,那如果我们需要维护一片连续的区域,又该使用什么办法呢?

与双指针算法维护指针指向的两个变量对应的是,滑动窗口也使用双指针,但维护的是两个指针所夹的区间[i,j]。


1.定长滑动窗口

LeetCode 2461:

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和:

  • 子数组的长度是 k,且
  • 子数组中的所有元素 各不相同 。

返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件,返回 0 。

子数组 是数组中一段连续非空的元素序列。

示例 1:

输入:nums = [1,5,4,2,9,9,9], k = 3
输出:15
解释:nums 中长度为 3 的子数组是:
- [1,5,4] 满足全部条件,和为 10 。
- [5,4,2] 满足全部条件,和为 11 。
- [4,2,9] 满足全部条件,和为 15 。
- [2,9,9] 不满足全部条件,因为元素 9 出现重复。
- [9,9,9] 不满足全部条件,因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和,所以返回 15 。

思路

所谓维护两指针之间的长度为k的区域,就是利用额外的数据结构储存这段区域的特征。

定长滑动窗口的流程无非是两步:

①展开窗口并创建初始数据结构

②移动窗口并维护过程数据结构

对于本题,我们使用两个数据结构维护区间特征:哈希表和一个单变量sum。不同的题目自有不同的要求。

第一步:先展开窗口到k的大小,我们创建哈希表储存其中数字出现的次数。

当窗口长度达到k时,我们的初始数据结构哈希表也就创建好了。

unordered_map<int,int>cnt;
const int n=nums.size();
long long ans=0,sum=0;
for(int i=0;i<k;i++){cnt[nums[i]]++;sum+=nums[i];
}
if(cnt.size()==k)ans=sum;

一个值得注意的点是,如果哈希表的键值对数量(也就是哈希表的size)正好是k的话,那么这个初始展开的窗口就是有效的,应该令ans=sum,表示我们考虑此为第一种可能得答案。

第二步:窗口开始滑动,哈希表和sum抛出不需再维护的特征。

*注意*:在一轮循环开始是,j位置是窗口右边界(包含j)移动到的位置,因此每轮循环维护的区域是[j-k+1,j]。

抛出j-k,即左边界外的那个位置,当哈希表维护的对应值为0时,我们使用erase彻底将其在哈希表中抹除,以免无效键值对污染哈希表的size。

for(int j=k;j<n;j++){cnt[nums[j-k]]--,cnt[nums[j]]++;if(!cnt[nums[j-k]])cnt.erase(nums[j-k]);sum=sum-nums[j-k]+nums[j];if(cnt.size()==k)ans=max(ans,sum);
}
return ans;

时时更新ans,维护其最大性质。 

复杂度

时间复杂度:O(n) 

Code

class Solution {
public:long long maximumSubarraySum(vector<int>& nums, int k) {unordered_map<int,int>cnt;const int n=nums.size();long long ans=0,sum=0;for(int i=0;i<k;i++){cnt[nums[i]]++;sum+=nums[i];}if(cnt.size()==k)ans=sum;for(int j=k;j<n;j++){cnt[nums[j-k]]--,cnt[nums[j]]++;if(!cnt[nums[j-k]])cnt.erase(nums[j-k]);sum=sum-nums[j-k]+nums[j];if(cnt.size()==k)ans=max(ans,sum);}return ans;}
};

2.不定长滑动窗口

LeetCode 2958:

给你一个整数数组 nums 和一个整数 k 。

一个元素 x 在数组中的 频率 指的是它在数组中的出现次数。

如果一个数组中所有元素的频率都 小于等于 k ,那么我们称这个数组是  数组。

请你返回 nums 中 最长好 子数组的长度。

子数组 指的是一个数组中一段连续非空的元素序列。

示例 1:

输入:nums = [1,2,3,1,2,3,1,2], k = 2
输出:6
解释:最长好子数组是 [1,2,3,1,2,3] ,值 1 ,2 和 3 在子数组中的频率都没有超过 k = 2 。[2,3,1,2,3,1] 和 [3,1,2,3,1,2] 也是好子数组。
最长好子数组的长度为 6 。

思路

不定长窗口和定长窗口的滑动本质上并无不同,尽管它看起来更难。

仍然,我们使用数据结构维护区间特征,只不过这次,左边界移动的条件是通过访问数据结构来达到的

具体的,我们会使用外层for循环控制右边界j的移动,而左边界的移动i则有内层while循环来实现。while循环的条件取决于维护[i,j]特征的数据结构,当特征不满足题意时,i左移抛出最左侧特征,并更新数据结构,一直循环到满足题意为止,则我们得到了[i,j]有效窗口区。

不定长滑动窗口的流程可以直接套模板,用伪代码展现的话,应该是这样的:

{

     某数据结构 data;

     int ans=0;

     for(j遍历nums){

         data加入nums[j]特征;

         while(i<j&&data不满足题设条件)数据结构抛出nums[i],i++;

         if(data满足题设条件)更新ans;

      }

}

对于本题,数据结构data应为一张记录了元素出现次数的哈希表。

同时,所谓“data不满足题设条件”只需要研究nums[j]即可,因为对于j之前的元素,上一次外层for循环会保证其满足题设条件。

*注意*:更新ans时要确保当前满足题设条件,因为i==j也会退出while循环。

复杂度

时间复杂度:O(n) 

复杂度分析:

时间分析: {

指针j共遍历数组一次,复杂度为O(n)

指针i虽在内层循环,但只前进不倒退,复杂度为O(n)

故整体复杂度为O(n)

}

Code

class Solution {
public:int maxSubarrayLength(vector<int>& nums, int k) {unordered_map<int,int>hash;const int n=nums.size();int ans=0;for(int i=0,j=0;j<n;j++){hash[nums[j]]++;while(i<j&&hash[nums[j]]>k)hash[nums[i++]]--;if(hash[nums[j]]<=k)ans=max(ans,j-i+1);}return ans;}
};

总结

滑动窗口是一类经典的双指针问题,它会借用额外的存储结构来维护一段连续的子数组。

但需要注意的是,一旦出现负数,它会变得极其被动,这是由于我们期望滑动窗口维护的区间特征总是右增左减的。


http://www.ppmy.cn/embedded/115218.html

相关文章

Kafka 下载安装及使用总结

1. 下载安装 官网下载地址&#xff1a;Apache Kafka 下载对应的文件 上传到服务器上&#xff0c;解压 tar -xzf kafka_2.13-3.7.0.tgz目录结果如下 ├── bin │ └── windows ├── config │ └── kraft ├── libs ├── licenses └── site-docs官方文档…

【加密算法基础——AES加密CBC模式和CFB模式的差异分析】

AES 解密实践之代码实现 上篇提到对于AES解密&#xff0c;命令行无法处理key截断的问题。 看一下实测代码&#xff0c;目前只测试到OpenSSL可以正确解密&#xff0c;但是库函数无法正确解密。 1. CFB模式代码展示 from Crypto.Cipher import AES import base64 import binas…

【Python报错已解决】 Requests.exceptions.ProxyError: HTTPSConnectionPool

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏: 《C干货基地》《粉丝福利》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 专栏介绍 在软件开发和日常使用中&#xff0c;BUG是不可避免的。本专栏致力于为广大开发者和技术爱好者提供一个关于BUG解决的经…

JavaEE: 创造无限连接——网络编程中的套接字

文章目录 Socket套接字TCP和UDP的区别有连接/无连接可靠传输/不可靠传输面向字节流/面向数据报全双工/半双工 UDP/TCP api的使用UDPDatagramSocketDatagramPacketInetSocketAddress练习 TCPServerSocketSocket练习 Socket套接字 Socket是计算机网络中的一种通信机制&#xff0…

Kafka 为什么这么快?

Kafka 是一款性能非常优秀的消息队列&#xff0c;每秒处理的消息体量可以达到千万级别。今天来聊一聊 Kafka 高性能背后的技术原理。 1 批量发送 Kafka 收发消息都是批量进行处理的。我们看一下 Kafka 生产者发送消息的代码&#xff1a; private Future<RecordMetadata>…

C# 中Faker

在 C# 中&#xff0c;Faker 类通常用于生成模拟数据&#xff08;也称为虚拟数据、测试数据&#xff09;&#xff0c;这对于开发、测试以及演示应用程序非常有用。一个流行的库叫做 Faker&#xff0c;它提供了一种简单的方式来生成各种随机数据。 安装 Faker 库 要使用 Faker …

【webpack4系列】webpack基础用法(二)

文章目录 entryoutputloaderpluginmode前端构建基础配置关联HTML插件html-webpack-plugin构建 CSS 解析 ES6和React JSX解析 ES6解析 React JSX 解析CSS、Less和Sass解析CSS解析Less解析sass 解析图片和字体资源解析&#xff1a;解析图片资源解析&#xff1a;解析字体资源解析&…

【JVM】符号引用 和 直接引用

符号引用 vs. 直接引用 在计算机科学中&#xff0c;特别是在编译原理和虚拟机技术中&#xff0c;涉及到两个概念&#xff1a;符号引用&#xff08;Symbolic Reference&#xff09;和直接引用&#xff08;Direct Reference&#xff09;。 符号引用&#xff08;Symbolic Refere…