LeetCode Hot100 滑动窗口 + 前缀和专项题解笔记
本次整理三道高频连续子数组/子串经典题3.无重复字符的最长子串滑动窗口438.找到字符串中所有字母异位词定长滑动窗口560.和为K的子数组前缀和哈希无法用滑动窗口核心区分✅ 滑动窗口适用区间满足单调性右边界扩张时左边界只会单向右移❌ 数组存在负数时区间和不具备单调性不能滑动窗口改用前缀和哈希。3. 无重复字符的最长子串题目大意找出字符串中不含重复字符的最长连续子串长度。思路不定长滑动窗口双指针left、rightHashSet维护窗口内字符右指针不断向右扩张遇到重复字符时不断移动左指针并删除窗口内字符直到当前字符不存在窗口中。classSolution{publicintlengthOfLongestSubstring(Strings){char[]sss.toCharArray();// set保存当前窗口[left, right]内所有字符SetCharactersetnewHashSet();intres0;// 右指针持续向右遍历for(intleft0,right0;rights.length();right){charchss[right];// 当前字符已经存在窗口不断收缩左边界while(set.contains(ch)){set.remove(ss[left]);left;}// 将当前右指针字符加入窗口set.add(ss[right]);// 更新最大窗口长度resMath.max(res,right-left1);}returnres;}}关键点while而不是if重复字符可能不在窗口最左侧需要持续左移直到无重复子串必须连续窗口区间[left,right]永远代表合法无重复区间。438. 找到字符串中所有字母异位词题目大意在s中找到所有p的字母异位词子串返回起始下标。异位词字母组成、数量完全相同顺序不同。思路定长滑动窗口窗口长度固定等于p的长度使用数组统计字符频次对比频次数组判断是否为异位词。classSolution{publicListIntegerfindAnagrams(Strings,Stringp){intsLens.length(),pLenp.length();ListIntegeransnewArrayList();// s长度小于p不可能存在异位词直接返回空集合if(sLenpLen){returnans;}// 频次数组仅小写字母大小26int[]sCountnewint[26];int[]pCountnewint[26];// 初始化第一个窗口填充p长度的字符for(inti0;ipLen;i){sCount[s.charAt(i)-a];pCount[p.charAt(i)-a];}// 第一个窗口匹配成功起始下标0加入结果if(Arrays.equals(sCount,pCount)){ans.add(0);}// 滑动窗口依次向右移动窗口for(inti0;isLen-pLen;i){// 移出窗口最左侧字符sCount[s.charAt(i)-a]--;// 纳入窗口右侧新字符sCount[s.charAt(ipLen)-a];// 频次数组完全相等 字母异位词if(Arrays.equals(sCount,pCount)){ans.add(i1);}}returnans;}}关键点定长窗口窗口宽度固定为p.length字母异位词等价于字符频次完全一致不用排序字符串数组对比效率更高每次滑动只修改左右两个字符的计数不需要重新统计整个窗口。560. 和为 K 的子数组题目大意统计数组中和等于k的连续子数组数量。数组存在负数思路前缀和 哈希表。定义前缀和pre[i] nums[0] nums[1] … nums[i]区间[j1, i]的和 pre[i] - pre[j]我们要求pre[i] - pre[j] k→pre[j] pre[i] - k哈希表记录每个前缀和出现的次数遍历到当前pre时查询pre-k存在多少次就是满足条件的子数组数量。classSolution{publicintsubarraySum(int[]nums,intk){intcount0;// 答案计数intpre0;// 当前前缀和// key前缀和value该前缀和出现次数HashMapInteger,IntegermapnewHashMap();// 初始化前缀和为0出现1次处理pre刚好等于k的场景map.put(0,1);for(inti0;inums.length;i){prenums[i];// 存在pre-k累加对应的出现次数if(map.containsKey(pre-k)){countmap.get(pre-k);}// 更新当前前缀和出现次数map.put(pre,map.getOrDefault(pre,0)1);}returncount;}}关键点数组包含负数区间和不单调不能使用滑动窗口map.put(0,1)必不可少例如nums[1],k1pre1pre-k0需要初始前缀和0先查询再put避免把当前pre计入本次查询保证区间是连续子数组。三道题目对比总结无重复最长子串不定长滑动窗口窗口约束「无重复字符」左右指针单向移动字母异位词定长滑动窗口窗口长度固定使用频次数组快速匹配异位词和为K子数组前缀和哈希。数组有负数时滑动窗口失效属于滑动窗口题的重要边界区分。

相关新闻

深入解析C55x DSP底层驱动:PLL、PWR、RTC与TIMER模块实战指南

深入解析C55x DSP底层驱动:PLL、PWR、RTC与TIMER模块实战指南

1. 项目概述:从寄存器到驱动,掌握C55x DSP的底层脉搏如果你在嵌入式领域,尤其是数字信号处理(DSP)方向摸爬滚打过一阵子,一定会对“芯片支持库”(Chip Support Library, CSL&#xf…

2026/11/19 22:03:54 阅读更多 →
技术笔记:KV Cache友好的上下文设计(李博杰《深入理解 AI Agent》2.3观后总结)

技术笔记:KV Cache友好的上下文设计(李博杰《深入理解 AI Agent》2.3观后总结)

背景 大模型每生成一个新token,都需要引用前文所有token的注意力中间结果。如果没有缓存优化,计算开销会随着上下文长度急剧上升。 KV Cache 的核心思路:缓存已经计算完毕token对应的Key、Value向量。在单次推理内部,只计算新增t…

2026/11/18 19:31:58 阅读更多 →
深入解析DSP/BIOS PIP模块:生产者-消费者模型与帧管理实战

深入解析DSP/BIOS PIP模块:生产者-消费者模型与帧管理实战

1. 项目概述与核心价值在嵌入式实时系统开发,尤其是基于德州仪器(TI)DSP芯片的应用中,任务间的数据流高效、可靠传递是决定系统性能的关键。想象一下,你的系统里有一个高速运行的ADC(模数转换器&#xff09…

2026/11/6 11:01:21 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/19 21:38:27 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/19 21:38:49 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/19 21:39:09 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/19 21:36:50 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/19 21:37:45 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/19 21:36:20 阅读更多 →

日新闻

周新闻

月新闻