算法篇（九）【滑动窗口】
如果在分析一道算法题的时候，发现使用的两个 ”双指针“ ， 都是同向的 ， 不回退的 ， 且一直都在维护 “一段连续的区间” ， 此时我们可以考虑使用 “滑动窗口” ！
一、长度最小的子数组
209. 长度最小的子数组 - 力扣（LeetCode）
此时，利用解法二，时间复杂度降到了O(n) 级别的 ， 是很优秀的算法了！！！
利用滑动窗口模拟示例一：
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size(),sum = 0,len = INT_MAX;for(int left = 0,right=0;right < n;right++){//1.进窗口 -> 并计算sumsum += nums[right];//2.出窗口 -> 如果sum >= targetwhile(sum >= target){//3.更新数据len = min(len,right-left+1);sum -= nums[left++];}}return len == INT_MAX ? 0 : len;}
};为何滑动窗口可以解决问题，并且时间复杂度更低？
简单的总结一句：就是利用了单调性 ， 规避许多没有必要的枚举行为！
二 、无重复字符的最长子串
3. 无重复字符的最长子串 - 力扣（LeetCode）
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = {0};//使用数组来模拟哈希表int left =0 ,right = 0 , n = s.size();int ret = 0;while(right < n){hash[s[right]]++;//进入窗口while(hash[s[right]]>1)//判断{hash[s[left++]]--;//出窗口}ret = max(ret , right - left +1);//更新结果right++;//让下一个元素进入窗口}return ret;}
};三、最大连续1的个数
1004. 最大连续1的个数 III - 力扣（LeetCode）
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int zero = 0,n = nums.size();int ret = 0;for(int left = 0,right = 0;right<n;right++){//1.进窗口if(nums[right] == 0)zero++;//2.判断while(zero > k){//3.出窗口if(nums[left] == 0)zero--;left++;}//4.更新数据ret = max(ret , right - left +1);}return ret;}
};四、将 x 减到 0 的最小操作数
1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）
题目要求的是数组[左端 + 右端] 两端连续的 、 和为 x 的最短数组 ， 信息量会稍微多一些 ， 不易理清思路 。
正难求反，既然常规的方法太复杂，那么我们另辟新路 ， 我们可以转化成求数组内一段连续的、和为 sum(nums) - x 的最长数组 ， 这个时候就可以用我们熟悉的滑动窗口来解决问题了。
但是这里需要注意一下 ， 当target 为 负数的时候 ， 区间内所有的值都小于目标值 ，此时直接返回 -1 即可 。
class Solution {
public:int minOperations(vector<int>& nums, int x) {int n = nums.size(),sum = 0;for(int i = 0;i<n;i++)sum+=nums[i];int tmp = -1;int target = sum - x , ret = 0;if(target < 0)return -1;for(int left = 0,right = 0;right < n ;right++){//1.进窗口ret += nums[right];//2.判断while(ret > target){//3.出窗口ret -= nums[left++];}if(ret == target)tmp = max(tmp,right - left +1);}if(tmp == -1) return tmp;else return nums.size() - tmp;}
};五、水果成篮
904. 水果成篮 - 力扣（LeetCode）
class Solution {
public:int totalFruit(vector<int>& f) {//统计窗口内出现了多少种水果unordered_map<int,int> hash;int ret = 0;for(int left = 0,right = 0;right<f.size();right++){//1.进窗口hash[f[right]]++;//2.判断while(hash.size()>2){//3.出窗口hash[f[left]]--;if(hash[f[left]]==0)hash.erase(f[left]);left++;}//4.更新结果ret = max(ret,right-left+1);}return ret;}
};六、找到字符串中所有字母异位词
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;//统计字符串 p 中每个字符出现的个数int hash1[26] = {0};for(auto ch : p)hash1[ch - 'a']++;//统计窗口里面的每一个字符出现的个数int hash2[26] = {0};int m = p.size();int count = 0;for(int left = 0,right = 0;right < s.size();right++){//1.进窗口 + 维护countchar in = s[right];if(++hash2[in - 'a'] <= hash1[in-'a'])count++;//2.判断if(right - left + 1 > m){char out = s[left++];//3.出窗口 + 维护countif(hash2[out - 'a']-- <= hash1[out - 'a'])count--;}//4.更新结果if(count == m)ret.push_back(left);}return ret;}
};
相关文章：
算法篇（九）【滑动窗口】
如果在分析一道算法题的时候，发现使用的两个 ”双指针“ ， 都是同向的 ， 不回退的 ， 且一直都在维护 “一段连续的区间” ， 此时我们可以考虑使用 “滑动窗口” ！ 一、长度最小的子数组 209. 长度最小的子…...
【AI面试准备】传统测试工程师Prompt Engineering转型指南
介绍技能转型：传统测试工程师需掌握Prompt Engineering优化AI输出。如何快速掌握，以及在实际工作中如何运用。 传统测试工程师向AI时代的技能转型，掌握Prompt Engineering（提示工程）已成为提升工作效率、适应智能化测…...
数字智慧方案6186丨智慧应急指挥解决方案（43页PPT）（文末有下载方式）
资料解读：智慧应急指挥解决方案 详细资料请看本解读文章的最后内容。 在当今社会，各类突发事件频发，应急管理工作面临着巨大挑战。智慧应急指挥解决方案应运而生，旨在提升应急管理的效率和水平，保障人民生命财产安全。…...
d202552-sql
一、184. 部门工资最高的员工 - 力扣（LeetCode） 要找到每个部门工资最高的 使用窗口函数 加排序函数 排序函数用rank dense_rank都行 把最高相同的找出来就行 select *, dense_rank() over(partition by departmentId order by Salary desc) as rank …...
cpper 转 java
快速上手 java 特性 文章目录 java 语言特点JVM工作过程组成 java 语言特点 Java 程序编译成字节码，然后由 Java 虚拟机（JVM）执行 不同平台适配相同的 JVM ，从而使得 Java 程序具备跨平台性 —— 一次编写，到处运行 …...
PostgreSQL常用函数
常用函数 数值函数 名称作用AVG(col)列的平均值COUNT(col)列的行数MAX(col)列的最大值MIN(col)列的最小值SUM(col)列值求和 字符串函数 名称作用LENGTH(str)计算字符串长度CONCAT(str1,str2)合并字符串LTRIM(col,str)从字串string的开头删除只包含str(默认空白LTRIM(col))R…...
P2196 [NOIP 1996 提高组] 挖地雷
P2196 [NOIP 1996 提高组] 挖地雷 - 洛谷 题目描述 在一个地图上有N（N ≤ 20）个地窖，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷&#…...
截图软件、画图软件、左右分屏快捷键
截图软件 画图软件 画图时候按字母可以改变颜色：红色r,蓝色b,绿色g,粉色p,橙色o 左右分屏：...
小刚说C语言刷题—1018三角形类别
1.题目描述 输入三个整数，以这三个数为边长，判断是否构成三角形；若不能输出 no 。 若构成三角形，进一步判断它们构的是：锐角三角形或直角三角形或钝角三角形。 分别输出 ruijiao , zhijiao , dunjiao 。 输入 三个…...
【Linux】PetaLinux开发
使用Xilinx的PetaLinux工具编译用于Zynq7020的Linux. 部分图片和经验来源于网络，若有侵权麻烦联系我删除，主要是做笔记的时候忘记写来源了，做完笔记很久才写博客。 专栏目录：记录自己的嵌入式学习之路-CSDN博客 目录 1 一般开发流程 2 离线编译过程 3 系统根文…...
【计算机网络网络层深度解析】从IP协议到路由优化
目录 前言技术背景与价值当前技术痛点解决方案概述目标读者说明 一、技术原理剖析核心概念图解核心作用讲解关键技术模块说明技术选型对比 二、实战演示环境配置要求核心实验实现实验1：IPv6地址配置实验2：OSPF路由配置实验3：NAT转换验证 运行…...
第 12 届蓝桥杯 C++ 青少组中 / 高级组省赛 2021 年真题
一、选择题 第 1 题 题目：下列符号中哪个在 C++ 中表示行注释 ( )。 A. ! B. # C. ] D. // 正确答案：D 答案解析： 在 C++ 中，//用于单行注释（行注释），从//开始到行末的内容会被编译器忽略。选项 A（!）、B（#）、C（]）均无注释功能，其中#常用于预处理指令（如#inclu…...
【quantity】5 derive_more库 2.0 版介绍
derive_more 是一个 Rust 过程宏库，旨在通过派生宏自动生成常见 trait 的实现，减少样板代码。2.0 版本带来了多项改进和新特性。 主要特性 1. 支持的 Trait 派生 derive_more 2.0 支持派生以下 trait： 基本操作 trait: Display - 格式化显…...
Qt编译报错:Unexpected compiler version, expected Clang 18.0.0 or newer——Qt安装MSVC编译器
截止到本人所使用的Qt6.6.3为止，Qt尚不支持MSVC2022编译器的默认编译器配制。所以，在Qt构建套件中使用MSVC编译器的话，可能仍需要调整Visual Studio版本，或者手动设置MSVC编译器。 如果你的系统安装的是Visual Studio2022&#x…...
（转）角色与动画的性能优化 | UnrealFest演讲干货
八、蓝图 8.1. Tick 优化的重点关注对象——Tick事件。在不需要的情况下，请默认关闭Tick。 在蓝图中Actor上关掉还不行，Component也需要关掉。 在CPP中，我们可以从PrimaryActorTick或PrimaryComponentTick中关闭Tick。 如果需要Tick&…...
小程序云开发-环境配置
如果点 云开发 没有反应，需要修改软件安装目录不要有中文，但软件名可以是中文： 首次使用，会送1个月的云开发，配置后要等10分钟以后，才可以使用 如果不能选择环境，关掉重新打开一次。 然后记…...
【c++】【STL】priority_queue详解
目录 priority_queue的作用priority_queue的接口构造函数emptysizetoppushpopswap priority_queue的实现仿函数（函数对象）是什么？向上调整算法（adjustup）向下调整算法（adjustdown）迭代器构造pus…...
C语音中的三元运算符
一、三元运算符的基本语法 三元运算符，也被称为条件运算符，是 C 语言中唯一有三个操作数的运算符。它的语法格式为：condition ? expression1 : expression2。从语法结构可以看出，三元运算符由一个条件表达式和两个普通表达式组…...
C++模板知识
目录 引言 一、非类型模板参数 二、类模板的特化 （一）概念 （二）函数模板特化 （三）类模板特化 1. 全特化 2. 偏特化 （四）类模板特化应用示例 三、模板的分离编译 …...
MCP 探索：微软 Microsoft MarkItDown MCP ，可把 Word、Excel 等转换成 MarkDown 格式
简简单单 Online zuozuo： 简简单单 Online zuozuo 简简单单 Online zuozuo 简简单单 Online zuozuo 简简单单 Online zuozuo ：本心、输入输出、结果 简简单单 Online zuozuo ： 文章目录 MCP 探索：微软 Microsoft MarkItDown MCP ，可把 Word、Excel 等转换成 MarkDown 格式…...
文本中地理位置提取方法—正则和NLP模型
这里写目录标题 一、提取地址列后12个字二、正则表达式删除不需要的文本三、保留关键字并删除之后的字四、相似度计算，查重五、去重 大量的文本中识别数据，要充分考虑效率和准确率。本文的方案是通过正则和NLP门址模型联合识别的方案。 首先利用现有粗略…...
AI大模型-RAG到底能做些什么？
RAG常见的应用场景，有以下几个方面： 1.智能客服系统：比如电商领域，对客户提出的常见问题，进行自动回复。减少人力成本。 2.人力资源管理：一个新的员工，入职一家大型公司，公司中有各…...
【算法基础】冒泡排序算法 - JAVA
一、算法基础 1.1 什么是冒泡排序 冒泡排序是一种简单直观的比较排序算法。它重复地走访待排序的数列，依次比较相邻两个元素，如果顺序错误就交换它们，直到没有元素需要交换为止。 1.2 基本思想 比较相邻元素：从头开始…...
Nginx搭建test服务器
创建test域名 进入阿里云添加解析 创建域名：test.xxxxx.com 服务器复制项目代码 新建目录，Git拉取项目代码，安装上插件包 修改配置文件，启动测试服务 修改配置文件“服务器接口” 开启服务pm2 start app.js --name "t…...
依赖倒置原则
当然可以！这次我们来详细讲解 依赖倒置原则（DIP: Dependency Inversion Principle），它是 SOLID 五大设计原则中的压轴，也是最关键的“架构型原则”。 我将从： 什么是依赖倒置原则（定义&#x…...
PostgreSQL 的 VACUUM 与 VACUUM FULL 详解
PostgreSQL 的 VACUUM 与 VACUUM FULL 详解 一、基本概念对比 特性VACUUMVACUUM FULL定义常规维护操作，清理死元组激进重组操作，完全重写表数据锁级别不阻塞读写(共享锁)排他锁(阻塞所有操作)空间回收只标记空间为可用，不返还OS空间返还操作…...
SQL面试题——留存分析之使用bitmap 计算留存
使用bitmap 计算留存 之前我们说过，留存分析其实在企业数据分析中，是很基础但是也很重要的，留存分析可以反映产品的发展是否健康，是否可持续发展，之前我们介绍过，可以看看之前的文章 SQL面试题——留存分析 因为使用工具的限制，所以我们实现方式也会有所不同，之前我们…...
P2415集合求和 题解
P2415 集合求和 题解 公式推导： 设集合有 n 个元素，记为 a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1,a2,…,an。 每个子集要么包含某个元素，要么不包含。 我们固定某个元素 a k a_k ak，再从剩下的 n − 1 n -…...
【2025年五一数学建模竞赛】C题 完整论文 模型建立与求解
目录 2025年五一数学建模竞赛 C题完整论文：建模与求解 Matlab代码一、问题重述二、模型假设与符号说明2.1 模型基本假设2.2 符号说明 问题一：预测博主新增关注数问题二：预测用户的新关注行为问题三：预测用户在线状态及互动博主问题…...
wpf 输入框 在输入时去除水印
wpf ScrollViewer 在输入数据时去除水印 在WPF（Windows Presentation Foundation）中，ScrollViewer控件通常用于显示滚动内容。如果你想在ScrollViewer中使用数据输入（例如文本输入），并且希望在输入时去除水…...
数字智慧方案5857丨智慧机场解决方案与应用（53页PPT）（文末有下载方式）
资料解读：智慧机场解决方案与应用 详细资料请看本解读文章的最后内容。 随着科技的飞速发展，智慧机场的建设已成为现代机场发展的重要方向。智慧机场不仅提升了旅客的出行体验，还极大地提高了机场的运营效率。本文将详细解读沃土数字平台在…...
C语言-指针（二）
一级指针 一级指针指的是存储了变量地址的指针 一级指针的变量类型是 类型 * 一级指针的类型与变量的类型有些不同 例：int * p 前面的int * 是该地址的类型 int a 0; int * p a; 这里的指针 p 就是一级指针 二级指针 指针变量也是变量因此也会有地…...
React 组件prop添加类型
给函数的props做注解 import { useState } from reacttype Props { className:string,title?:string } // 自定义一个Button组件 function Button(props:Props){// 解构出classname\const {className} propsreturn <button className{className}>点击我</button&g…...
Spring Boot中集成Guava Cache或者Caffeine
一、在Spring Boot(1.x版本)中集成Guava Cache 注意： Spring Boot 2.x用户：优先使用Caffeine，性能更优且维护活跃。 1. 添加依赖 在pom.xml中添加Guava依赖： <dependency><groupId>com.google.guava</groupId&…...
全感官交互革命：当 AI 大模型学会 “看、听、说、创”
引言：从 “文字对话” 到 “全感官体验”，AI 正在重塑人类认知边界 当 AI 不再局限于文本对话，而是能 “看懂” 图像、“听懂” 语音、“生成” 视频，并将这些模态无缝融合时，一场关于人机交互的革命已然开启。DeepSe…...
Linux 库文件详解
Linux 库文件详解 一、库文件概述 库文件是预先编译好的方法的集合，它为程序员提供了一种方便的方式来复用代码。在 Linux 系统中，主要有两种类型的库文件：静态库和共享库。 静态库（.a 文件） 使用静态库࿰…...
蒙特卡罗方法（Monte Carlo Method）：基于随机采样的数值计算与模拟技术
核心思想 蒙特卡罗方法通过随机采样和统计模拟解决数学、物理、工程等领域的复杂问题，其核心是利用大数定律——当样本量足够大时，样本均值会收敛于期望值。 关键特点： 无维度诅咒&#x…...
HTTPS协议：更安全的HTTP
目录 1. 前言 2. HTTP 与 HTTPS：安全的分水岭 2.1 HTTP 的安全隐患 2.2 HTTPS 的安全提升 3. HTTPS 的核心概念 3.1 加密三剑客：对称加密、非对称加密与哈希算法 3.2 SSL/TLS 握手过程：建立安全通道的关键步骤 3.3 数字证书ÿ…...
Flutter BottomNavigationBar 详解
目录 一、引言 二、BottomNavigationBar 的基本用法 三、主要属性 1. 基本配置 2. 导航项配置 3. 导航类型选择 四、高级功能实现 1. 结合 PageView 实现滑动切换 2. 添加徽章提示 3. 自定义凸起按钮（FAB融合） 4. 渐变背景实现 五、自定义 B…...
吴恩达深度学习作业 RNN模型——字母级语言模型
一. 简单复习一下RNN RNN RNN适用于处理序列数据，令是序列的第i个元素，那么就是一个长度为的序列，NLP中最常见的元素是单词，对应的序列是句子。 RNN使用同一个神经网络处理序列中的每一个元素。同时，为了表示序列的…...
数字时代，如何为个人信息与隐私筑牢安全防线？
首席数据官高鹏律师团队编著 在当今数字化时代，个人信息和隐私保护至关重要。我们在享受数字生活带来的便利时，也面临着个人信息泄露、隐私被侵犯的风险。下面将从先进技术和法律途径两个方面，探讨如何严格保护个人信息和隐私。 一、先进技…...
javascript交换值最好三种
代码 1. 位运算(性能高，但只能用于整数) var a15; var b32; console.log(a) //15 console.log(b) //32 a a ^ b; b a ^ b; a a ^ b; console.log(a) //32 console.log(b) //152. 数组结构(性能高，但要ES6) var a15; var b32; console.log(…...
C++-Lambda表达式
目录 1.什么是 Lambda？ 2.例子：打印每个元素（和 for_each 一起用） 3.捕获外部变量（Capture） 3.1. 捕获值（拷贝）：[] 3.2. 捕获引用：[&] 3.3. 指定捕…...
逻辑回归的多分类实战：以鸢尾花数据集为例
文章目录 引言：从二分类到多分类一、多分类问题无处不在二、One-vs-All策略揭秘1. 核心思想2. 数学表达 三、鸢尾花分类完整实现1. 环境准备2. 数据加载与探索3. 数据预处理4. 模型训练与评估5. 决策边界可视化 四、关键参数解析五、总结 引言：从二分类到…...
[面试]SoC验证工程师面试常见问题（一）
SoC验证工程师面试常见问题（一） 摘要：在面试 SoC 验证工程师职位时，面试官通常会重点考察候选人对 SystemVerilog 和 UVM (Universal Verification Methodology) 的掌握程度，因为这两者是现代 IC 验证的核心技能。以下是可能会被问到的常见问题，涵盖 SystemVerilo…...
传统银行服务和 区块链支付无缝融合的一种解决方案
Dragonfly Capital 的合伙人 Alex Pack 曾表示：“DeFi 的目标是重构全球银行体系，并打造开放且无须许可的经营环境。”在 DeFi 的金融世界中，加密资产架构在区块链上，通过各个协议实现资产之间的高效转移和价值的实时流通，如 Metamask 钱包的自托管，Uniswap 的资产交易，…...
大语言模型能力评定探讨
有标准答案的评估（选择题） 评估语言模型能力的基本思路是准备输入和标准答案，比较不同模型对相同输入的输出 由于AI答题有各种各样答案，因此现在是利用选择题考察。 有一个知名的选择题的基准叫做Massive Multitask Language Und…...
解构区块链身份认证：从ID到零知识证明的实战指南
引言 在数字经济高速发展的今天，数字身份已成为个人与数字世界交互的核心凭证。传统中心化身份系统存在数据孤岛、隐私泄露、单点故障等痛点，而区块链技术凭借去中心化、不可篡改、可追溯的特性，为数字身份验证提供了革命性解决方案…...
IntelliJ IDEA 使用教程
文章目录 一、创建项目二、创建模块三、创建包四、创建类五、编写代码六、运行代码注意 一、创建项目 二、创建模块 【File】->【New】->【Module…】 三、创建包 【helloword】->【右击 src】->【New】->【Package】 四、创建类 【helloword】->【s…...
HBM的哪些事
命令操作 这也许是DDR往HBM演进的一些奇淫技巧。 本篇内容属于杂谈，关于HBM的奇淫技巧，随后出专题介绍。...