当前位置: 首页 > news >正文

C++滑动窗口技术深度解析:核心原理、高效实现与高阶应用实践

目录

一、滑动窗口的核心原理

二、滑动窗口的两种类型

1. 固定大小的窗口

2. 可变大小的窗口

三、实现细节与关键点

1. 窗口的初始化

2. 窗口的移动策略

3. 结果的更新时机

四、经典问题与代码示例

示例 1:和 ≥ target 的最短子数组(可变窗口)

示例 2:无重复字符的最长子串(哈希表辅助)

五、边界条件与易错点

1. 数组越界

2. 初始值的设置

3. 哈希表的使用

4. 循环条件错误

六、时间复杂度分析

七、滑动窗口的适用场景

八、滑动窗口的扩展

1. 结合前缀和

2. 结合单调队列

总结


一、滑动窗口的核心原理

        滑动窗口(Sliding Window) 是一种基于 双指针(Two Pointers) 的算法设计范式,核心思想是通过维护一个 动态窗口区间[left, right]),在遍历过程中调整窗口的左右边界,避免重复计算,从而将时间复杂度优化到 O(n)

  • 核心逻辑

    • 窗口扩张right 指针向右移动,扩大窗口,直到满足某个条件。

    • 窗口收缩:一旦满足条件,left 指针向右移动,缩小窗口,直到不满足条件。

    • 更新结果:在窗口调整过程中,记录最优解。


二、滑动窗口的两种类型

1. 固定大小的窗口
  • 特点:窗口长度固定为 k,通过滑动窗口的起始位置遍历所有可能的子区间。

  • 典型问题

    • 求长度为 k 的子数组的最大平均值

    • 长度为 k 的子字符串的排列匹配

C++ 代码模板

int fixedWindow(vector<int>& nums, int k) 
{int sum = 0, max_sum = 0;// 初始化窗口for (int i = 0; i < k; ++i) sum += nums[i];max_sum = sum;// 滑动窗口for (int right = k; right < nums.size(); ++right) {sum += nums[right] - nums[right - k]; // 窗口右移,更新和max_sum = max(max_sum, sum);}return max_sum;
}
2. 可变大小的窗口
  • 特点:窗口大小不固定,根据问题条件动态调整 left 和 right 指针。

  • 典型问题

    • 无重复字符的最长子字符串

    • 和大于等于 target 的最短子数组

C++ 代码模板

int variableWindow(string s) 
{unordered_map<char, int> window;int left = 0, max_len = 0;for (int right = 0; right < s.size(); ++right) {char c = s[right];window[c]++; // 窗口扩张// 窗口收缩条件:出现重复字符while (window[c] > 1) {char d = s[left];window[d]--; // 移出左边界字符left++;}max_len = max(max_len, right - left + 1); // 更新结果}return max_len;
}

三、实现细节与关键点

1. 窗口的初始化
  • 初始指针位置:通常 left = right = 0

  • 状态变量:如窗口内的和(sum)、哈希表(记录字符频率)等。

2. 窗口的移动策略
  • 扩张条件:一般通过 for 循环逐步移动 right

  • 收缩条件:在满足特定条件时,通过 while 循环移动 left,直到条件不满足。

3. 结果的更新时机
  • 固定窗口:每次窗口滑动后更新结果。

  • 可变窗口:在窗口收缩后或扩张过程中更新结果。


四、经典问题与代码示例

示例 1:和 ≥ target 的最短子数组(可变窗口)
int minSubArrayLen(int target, vector<int>& nums) 
{int left = 0, sum = 0;int min_len = INT_MAX;for (int right = 0; right < nums.size(); ++right) {sum += nums[right]; // 窗口扩张while (sum >= target) { // 窗口收缩条件min_len = min(min_len, right - left + 1);sum -= nums[left++]; // 窗口收缩}}return min_len == INT_MAX ? 0 : min_len;
}
示例 2:无重复字符的最长子串(哈希表辅助)
int lengthOfLongestSubstring(string s) 
{unordered_map<char, int> last_pos; // 记录字符最后出现的位置int left = 0, max_len = 0;for (int right = 0; right < s.size(); ++right) {char c = s[right];// 若字符 c 已存在且在窗口内,移动 left 到 last_pos[c] + 1if (last_pos.count(c) && last_pos[c] >= left) {left = last_pos[c] + 1;}last_pos[c] = right; // 更新字符位置max_len = max(max_len, right - left + 1);}return max_len;
}

五、边界条件与易错点

1. 数组越界
  • 在固定窗口中,需确保 right - k >= 0

  • 在可变窗口中,需检查 left 是否超过 right

2. 初始值的设置
  • 最小值初始化为 INT_MAX,最大值初始化为 INT_MIN

3. 哈希表的使用
  • 在字符频率统计中,需确保哈希表的键存在性(如用 count() 检查)。

4. 循环条件错误
  • 错误:在收缩窗口时使用 if 而非 while,导致窗口未完全收缩。

  • 正确:使用 while 循环确保窗口收缩到条件不满足。


六、时间复杂度分析

  • 固定窗口:O(n),每个元素被访问一次。

  • 可变窗口:O(n),每个元素最多被 left 和 right 各访问一次。


七、滑动窗口的适用场景

  1. 连续子数组/子字符串问题

    • 最短/最长满足条件的子数组

    • 子数组的和/乘积/频率统计

  2. 优化暴力解法

    • 将 O(n²) 的暴力枚举优化为 O(n)

  3. 数据流处理

    • 实时处理数据流中的窗口统计量(如移动平均值)


八、滑动窗口的扩展

1. 结合前缀和
  • 用于处理负数数组或更复杂的条件(如子数组和为 k)。

  • 示例代码:

    int subarraySum(vector<int>& nums, int k) 
    {unordered_map<int, int> prefix_sum; // 前缀和 -> 出现次数prefix_sum[0] = 1;int sum = 0, count = 0;for (int num : nums) {sum += num;if (prefix_sum.count(sum - k)) {count += prefix_sum[sum - k];}prefix_sum[sum]++;}return count;
    }
2. 结合单调队列
  • 用于维护窗口内的最大值/最小值(如滑动窗口最大值问题)。

  • 示例代码:

    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {deque<int> dq; // 存储下标,按值单调递减vector<int> res;for (int i = 0; i < nums.size(); ++i) {// 移除超出窗口的元素if (!dq.empty() && dq.front() == i - k) dq.pop_front();// 维护单调队列while (!dq.empty() && nums[i] >= nums[dq.back()]) dq.pop_back();dq.push_back(i);// 记录窗口最大值if (i >= k - 1) res.push_back(nums[dq.front()]);}return res;
    }

总结

滑动窗口的核心在于 双指针的协同移动 和 窗口状态的动态维护。掌握以下要点:

  1. 明确窗口的 扩张与收缩条件

  2. 合理选择 数据结构(如哈希表、单调队列)维护窗口状态。

  3. 注意 边界条件 和 初始值设置

  4. 灵活结合其他算法(如前缀和、单调队列)解决复杂问题。

相关文章:

C++滑动窗口技术深度解析:核心原理、高效实现与高阶应用实践

目录 一、滑动窗口的核心原理 二、滑动窗口的两种类型 1. 固定大小的窗口 2. 可变大小的窗口 三、实现细节与关键点 1. 窗口的初始化 2. 窗口的移动策略 3. 结果的更新时机 四、经典问题与代码示例 示例 1&#xff1a;和 ≥ target 的最短子数组&#xff08;可变窗口…...

基于构件的软件开发方法

摘要: 本人在2023年1月参与广东某公司委托我司开发的“虚拟电厂”项目,主要负责整体架构设计和中间件的选型,该项目为新型电力存储、电力调度、能源交易提供一整套的软件系统,包括设备接入、负载预测、邀约竞价、用户设备调控等功能。本项目以“虚拟电厂”项目为例,讨论基…...

网站快速收录:如何设置robots.txt文件?

本文转自&#xff1a;百万收录网 原文链接&#xff1a;https://www.baiwanshoulu.com/34.html 为了网站快速收录而合理设置robots.txt文件&#xff0c;需要遵循一定的规则和最佳实践。robots.txt文件是一个纯文本文件&#xff0c;它告诉搜索引擎爬虫哪些页面可以访问&#xff…...

OpenGL学习笔记(六):Transformations 变换(变换矩阵、坐标系统、GLM库应用)

文章目录 向量变换使用GLM变换&#xff08;缩放、旋转、位移&#xff09;将变换矩阵传递给着色器坐标系统与MVP矩阵三维变换绘制3D立方体 & 深度测试&#xff08;Z-buffer&#xff09;练习1——更多立方体 现在我们已经知道了如何创建一个物体、着色、加入纹理。但它们都还…...

8.攻防世界Web_php_wrong_nginx_config

进入题目页面如下 尝试弱口令密码登录 一直显示网站建设中&#xff0c;尝试无果&#xff0c;查看源码也没有什么特别漏洞存在 用Kali中的dirsearch扫描根目录试试 命令&#xff1a; dirsearch -u http://61.147.171.105:53736/ -e* 登录文件便是刚才登录的界面打开robots.txt…...

【优先算法】专题——位运算

在讲解位运算之前我们来总结一下常见的位运算 一、常见的位运算 1.基础为运算 << &&#xff1a;有0就是0 >> |&#xff1a;有1就是1 ~ ^&#xff1a;相同为0&#xff0c;相异位1 /无进位相加 2.给一个数 n&#xff0c;确定它的二进制表示…...

qt.qpa.plugin: Could not find the Qt platform plugin “dxcb“ in ““

个人博客地址&#xff1a;qt.qpa.plugin: Could not find the Qt platform plugin "dxcb" in "" | 一张假钞的真实世界 我遇到的场景是&#xff0c;在Deepin系统终端中运行PySide应用时&#xff0c;没有错误提示&#xff0c;但在VS Code中运行时&#xff…...

1-刷力扣问题记录

25.1.19 1.size()和.length()有什么区别 2.result.push_back({nums[i], nums[left], nums[right]});为什么用大括号&#xff1f; 使用大括号 {} 是 C11 引入的 初始化列表 语法&#xff0c;它允许我们在构造或初始化对象时直接传入一组值。大括号的使用在许多情况下都能让代码…...

物联网 STM32【源代码形式-使用以太网】连接OneNet IOT从云产品开发到底层MQTT实现,APP控制 【保姆级零基础搭建】

物联网&#xff08;IoT&#xff09;‌是指通过各种信息传感器、射频识别技术、全球定位系统、红外感应器等装置与技术&#xff0c;实时采集并连接任何需要监控、连接、互动的物体或过程&#xff0c;实现对物品和过程的智能化感知、识别和管理。物联网的核心功能包括数据采集与监…...

【单层神经网络】基于MXNet的线性回归实现(底层实现)

写在前面 基于亚马逊的MXNet库本专栏是对李沐博士的《动手学深度学习》的笔记&#xff0c;仅用于分享个人学习思考以下是本专栏所需的环境&#xff08;放进一个environment.yml&#xff0c;然后用conda虚拟环境统一配置即可&#xff09;刚开始先从普通的寻优算法开始&#xff…...

unity中的动画混合树

为什么需要动画混合树&#xff0c;动画混合树有什么作用&#xff1f; 在Unity中&#xff0c;动画混合树&#xff08;Animation Blend Tree&#xff09;是一种用于管理和混合多个动画状态的工具&#xff0c;包括1D和2D两种类型&#xff0c;以下是其作用及使用必要性的介绍&…...

《基于deepseek R1开源大模型的电子数据取证技术发展研究》

《基于deepseek R1开源大模型的电子数据取证技术发展研究》 摘要 本文探讨了基于deepseek R1开源大模型的电子数据取证技术发展前景。随着人工智能技术的快速发展&#xff0c;AI大模型在电子数据取证领域的应用潜力日益凸显。本研究首先分析了电子数据取证的现状和挑战&#xf…...

Potplayer常用快捷键

Potplayer是一个非常好用的播放器,功能强大 功能快捷键播放/暂停空格键退出Esc下一帧F上一帧D快进10秒→快退10秒←快进30秒Ctrl →快退30秒Ctrl ←快进1分钟Alt →快退1分钟Alt ←增加播放速度C减少播放速度X恢复正常速度Z增加音量↑减少音量↓静音M显示/隐藏字幕Ctrl A…...

C++ Primer 自定义数据结构

欢迎阅读我的 【CPrimer】专栏 专栏简介&#xff1a;本专栏主要面向C初学者&#xff0c;解释C的一些基本概念和基础语言特性&#xff0c;涉及C标准库的用法&#xff0c;面向对象特性&#xff0c;泛型特性高级用法。通过使用标准库中定义的抽象设施&#xff0c;使你更加适应高级…...

35.Word:公积金管理中心文员小谢【37】

目录 Word1.docx ​ Word2.docx Word2.docx ​ 注意本套题还是与上一套存在不同之处 Word1.docx 布局样式的应用设计页眉页脚位置在水平/垂直方向上均相对于外边距居中排列&#xff1a;格式→大小对话框→位置→水平/垂直 按下表所列要求将原文中的手动纯文本编号分别替换…...

北京钟鼓楼:立春“鞭春牛”,钟鼓迎春来

仁风导和气,勾芒御昊春。“钟鼓迎春”立春鞭春牛民俗体验活动于立春当日在北京钟鼓楼隆重举办。此次活动由北京市钟鼓楼文物保管所主办,京睿文(北京)文化科技有限公司承办,通过礼官报春、击鼓鸣钟、春娃喊春、中国时间文化角色巡游、鞭春牛等一系列精彩的活动环节,为观众呈现了…...

股票入门知识

股票入门&#xff08;更适合中国宝宝体制&#xff09; 股市基础知识 本文介绍了股票的基础知识&#xff0c;股票的分类&#xff0c;各板块发行上市条件&#xff0c;股票代码&#xff0c;交易时间&#xff0c;交易规则&#xff0c;炒股术语&#xff0c;影响股价的因素&#xf…...

Java自定义IO密集型和CPU密集型线程池

文章目录 前言线程池各类场景描述常见场景案例设计思路公共类自定义工厂类-MyThreadFactory自定义拒绝策略-RejectedExecutionHandlerFactory自定义阻塞队列-TaskQueue&#xff08;实现 核心线程->最大线程数->队列&#xff09; 场景1&#xff1a;CPU密集型场景思路&…...

Git的安装步骤详解(复杂的安装界面该如何勾选?)

目录 一、下载与安装 1.官网下载git 2、下载完成之后&#xff0c;双击下载好的exe文件进行安装 3、选择Git的安装路径 4、选择在安装 Git 时要包含的组件和功能 5、选择 Git 快捷方式在 Windows 开始菜单中的位置。 6、选择 Git 使用的默认编辑器 7、调整新仓库中初始分…...

文本预处理

一、文本的基本单位 1、Token 定义&#xff1a;文本的最小单位&#xff0c;例如单词、标点符号。 示例&#xff1a; 原句&#xff1a; "I love NLP." 分词结果&#xff1a; [I, love, NLP, .] 2、语法与语义 语法&#xff1a;词的结构和句子的组合规则。 语义&a…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...

规则与人性的天平——由高考迟到事件引发的思考

当那位身着校服的考生在考场关闭1分钟后狂奔而至&#xff0c;他涨红的脸上写满绝望。铁门内秒针划过的弧度&#xff0c;成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定"&#xff0c;构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...

CppCon 2015 学习:Time Programming Fundamentals

Civil Time 公历时间 特点&#xff1a; 共 6 个字段&#xff1a; Year&#xff08;年&#xff09;Month&#xff08;月&#xff09;Day&#xff08;日&#xff09;Hour&#xff08;小时&#xff09;Minute&#xff08;分钟&#xff09;Second&#xff08;秒&#xff09; 表示…...