首页/新闻资讯/正文详情

滑动窗口与哈希表解决字母异位词问题

发布时间:2026/11/5 8:37:17 来源:云帆数科 栏目:资讯中心
滑动窗口与哈希表解决字母异位词问题
1. 题目解析与核心概念1.1 题目重述与理解力扣第38题找到字符串中所有字母异位词要求我们给定一个字符串s和一个非空字符串p找到s中所有是p的字母异位词的子串返回这些子串的起始索引。字母异位词指字母相同但排列不同的字符串。举个例子输入s cbaebabacd, p abc输出[0, 6] 解释起始索引0的子串cba是abc的异位词起始索引6的子串bac是abc的异位词1.2 异位词的本质特征理解异位词的关键在于抓住其两个核心特征字符组成完全相同包括字符种类和每个字符的出现次数字符顺序可以不同这意味着判断两个字符串是否为异位词时我们实际上是在比较它们的字符频率分布是否一致。这个认知将直接影响我们后续的算法设计方向。1.3 暴力解法思路最直观的解法是滑动窗口暴力匹配计算p的字符频率分布在s上滑动一个长度为len(p)的窗口对每个窗口子串计算其字符频率与p的频率分布比较若匹配则记录起始索引这种解法时间复杂度为O(n×m)其中n是s的长度m是p的长度。虽然直观但效率不高特别是当字符串较长时。2. 优化解法滑动窗口与哈希表2.1 滑动窗口技术原理滑动窗口是处理字符串/数组子串问题的经典技术。其核心思想是维护一个大小固定的窗口在数据结构上滑动每次滑动时只对窗口两端的变化进行处理避免重复计算。对于本题窗口大小固定为len(p)窗口从s的最左端开始每次右移一位直到窗口右端到达s的末尾2.2 哈希表记录字符频率我们可以用哈希表或称为字典来记录字符频率。Python中可以使用collections.defaultdict或直接使用字典。关键操作初始化时统计p的字符频率称为need维护一个窗口频率统计称为window当window与need完全匹配时找到有效解2.3 有效匹配的判断优化直接比较两个哈希表是否相等效率不高。我们可以引入一个变量match来记录当前已匹配的字符种类数当window[c] need[c]时match加1当match等于need中不同字符的总数时说明完全匹配这样可以将每次比较的时间复杂度从O(m)降到O(1)3. 完整算法实现与代码解析3.1 Python实现代码from collections import defaultdict def findAnagrams(s: str, p: str) - List[int]: need defaultdict(int) window defaultdict(int) for c in p: need[c] 1 left, right 0, 0 valid 0 res [] while right len(s): c s[right] right 1 if c in need: window[c] 1 if window[c] need[c]: valid 1 while right - left len(p): if valid len(need): res.append(left) d s[left] left 1 if d in need: if window[d] need[d]: valid - 1 window[d] - 1 return res3.2 代码逐行解析初始化阶段创建need和window两个defaultdict用于记录字符频率遍历p填充need字典滑动窗口阶段使用left和right指针表示窗口左右边界valid记录当前已满足条件的字符种类数res存储结果索引右扩窗口每次将right右移获取新字符如果该字符在need中则更新window计数当某个字符计数达到need要求时valid加1左缩窗口当窗口大小等于len(p)时开始检查如果valid等于need的长度记录left索引左移left时如果移出的字符在need中需要更新window和valid3.3 复杂度分析时间复杂度O(n)其中n是s的长度。虽然有嵌套循环但每个字符最多被访问两次右扩和左缩各一次空间复杂度O(m)主要是哈希表的空间其中m是p中不同字符的数量4. 常见问题与调试技巧4.1 边界条件处理常见边界情况需要特别注意s比p短时直接返回空列表p为空字符串时根据题目描述p非空可不处理s或p中包含非字母字符题目通常保证输入合法大小写敏感问题题目通常说明是否区分大小写4.2 调试技巧当代码出现问题时可以添加打印语句检查打印need和window的实时状态在每次窗口移动时打印当前窗口内容检查valid的变化是否符合预期示例调试代码print(fWindow: {s[left:right]}, valid: {valid}) print(fNeed: {need}, Window: {window})4.3 算法变体与扩展固定窗口大小的滑动窗口 本题窗口大小固定为len(p)可以简化实现window_size len(p) for i in range(len(s) - window_size 1): window s[i:iwindow_size] # 检查window是否为p的异位词使用数组代替哈希表 如果字符集有限如只有小写字母可以用长度为26的数组代替哈希表need [0] * 26 for c in p: need[ord(c) - ord(a)] 1优化空间复杂度 可以只维护一个差值数组记录window与need的差异diff [0] * 26 # 初始化时设置diff为need的副本 # 每次窗口移动时调整diff # 当diff全为0时表示匹配5. 实战练习建议5.1 推荐练习题为了巩固滑动窗口和异位词的相关技巧建议尝试以下力扣题目找到字符串中所有字母异位词本题字符串的排列几乎相同最小覆盖子串进阶版无重复字符的最长子串滑动窗口基础有效的字母异位词简化版5.2 解题思路总结解决异位词相关问题的通用思路确认问题是否真的需要处理异位词有时可能只是子串使用哈希表或数组统计字符频率考虑滑动窗口技术优化遍历过程通过有效变量减少重复计算注意边界条件和特殊输入5.3 编码实现建议先写出暴力解法确保理解题意逐步引入优化哈希表→滑动窗口→有效变量使用小例子手动模拟算法过程添加详细的注释说明每个变量的作用编写测试用例覆盖各种边界情况6. 性能优化与进阶思考6.1 进一步优化思路虽然当前解法已经是较优的O(n)时间复杂度但在某些情况下还可以优化字符集有限时使用固定大小数组代替哈希表减少哈希计算开销并行计算对于超长字符串可以分割后并行处理不同区段预处理如果需要对同一个p查询多个不同的s可以预先计算p的频率分布6.2 其他算法思路除了滑动窗口还可以考虑双指针优化在某些情况下可以跳过不必要的检查Rabin-Karp算法使用滚动哈希来比较子串位图法对于特定字符集可以用位运算表示6.3 实际应用场景异位词检测在实际中有多种应用文本搜索与内容过滤生物信息学中的序列分析密码学中的排列组合分析自然语言处理中的词形变化识别理解这些基础算法有助于解决更复杂的实际问题。

相关推荐

零代码自动化开发实战:职场效率提升指南
零代码自动化开发实战:职场效率提升指南

1. 零代码自动化技能开发指南 上周帮市场部的同事解决了一个重复性工作问题,整个过程完全没写一行代码,却实现了每天节省2小时手工操作的效果。这让我意识到,很多非技术岗位的职场人其实都有类似的自动化需求,只是苦于不会编程而无… · 2026/11/5 8:37:17

北斗三号双频B1C/B2a MATLAB软件接收机捕获跟踪定位
北斗三号双频B1C/B2a MATLAB软件接收机捕获跟踪定位

简介:这套面向北斗三号软件接收机学习与二次开发的 MATLAB 工程,聚焦 B1C/B2a 双频信号处理,适合具备 GNSS 基础、希望从理论走向实现的高校学生、科研人员与 SDR 开发者。压缩包共 87 个文件,以 82 个 .m 脚本与函数为主体&#… · 2026/11/5 8:37:17

易飞ERP WebAPI审核接口设计与实现
易飞ERP WebAPI审核接口设计与实现

1. 项目背景与核心价值在企业资源计划(ERP)系统中,单据审核流程是业务流转的核心环节。传统ERP系统通常需要审核员登录桌面客户端进行操作,这种模式在移动办公场景下存在明显局限性。易飞ERP通过开放WebAPI接口实现全单据类型的审… · 2026/11/5 8:36:16

S120速度精度差排查指南:编码器信号与速度环调参实战
S120速度精度差排查指南:编码器信号与速度环调参实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 8:39:19

STM32F042配ADS122U04:UART接口24位ADC打造HVAC高精度测温方案
STM32F042配ADS122U04:UART接口24位ADC打造HVAC高精度测温方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 8:39:19

ADS122U04+MK20DN128VFM5打造高精度工业温度采集方案
ADS122U04+MK20DN128VFM5打造高精度工业温度采集方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 8:39:19

ADS122U04IPWR+PIC18F87K22实现工业HVAC高精度温度采集
ADS122U04IPWR+PIC18F87K22实现工业HVAC高精度温度采集

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 8:39:19

ADS122U04IPWR+STM32工业级温度测量全链路设计
ADS122U04IPWR+STM32工业级温度测量全链路设计

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 8:39:19

学术论文写作工具全解析:从LaTeX到Word公式编辑
学术论文写作工具全解析:从LaTeX到Word公式编辑

1. 论文写作工具全景概览学术写作从来不是单打独斗的过程。记得我博士期间为了赶一篇JCR一区论文,连续72小时对着Word文档调整公式格式的经历,让我深刻意识到专业工具的重要性。如今市面上涌现的论文辅助工具,早已从单纯的文字处理进化到涵盖… · 2026/11/5 8:38:17

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 6:59:29

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 7:02:38

多智能体协作系统架构设计与实践优化
多智能体协作系统架构设计与实践优化

1. 多智能体协作系统的时代背景2017年Transformer架构的诞生彻底改变了人工智能的发展轨迹。当行业还沉浸在单一大模型带来的性能突破时,Anthropic的研究团队已经将目光投向了更前沿的领域——如何让多个智能体通过协作产生超越单体能力的系统智能。这就像交响乐团中… · 2026/11/5 0:00:39

大模型系统性入门实战指南:从原理到部署微调的全链路路线
大模型系统性入门实战指南:从原理到部署微调的全链路路线

提到大模型的系统性入门,我先说个结论:这事真不难,难的是资料太散、路线太多,今天这个框架明天那个工具,新人很容易在“收藏夹吃灰”和“教程看到一半放弃”之间反复横跳。市面上关于大模型的内容少说有几十万篇&#… · 2026/11/5 0:00:39

鸿蒙文件系统沙箱机制解析与开发实践
鸿蒙文件系统沙箱机制解析与开发实践

1. 鸿蒙文件系统沙箱机制深度解析作为一名从Android转向鸿蒙开发的工程师,我深刻体会到文件系统访问是迁移过程中最先遇到的"拦路虎"。在Android上运行良好的文件读写代码,在鸿蒙真机环境却频频出现文件写入后神秘消失或直接抛出权限拒绝错误的… · 2026/11/5 0:00:39

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 6:59:29

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 7:02:38

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码