宜昌制作网站公司淄博网站建设公司推荐

宜昌制作网站公司,淄博网站建设公司推荐,房产备案查询网上查询系统,wordpress 广播条引言 对于初学编程的小伙伴来说#xff0c;LeetCode 中的字符串匹配类题目常常让人头疼 —— 既要处理复杂的字符组合#xff0c;又要兼顾效率#xff0c;很容易陷入 “暴力破解超时” 的困境。 今天要讲的第 30 题 “串联所有单词的子串”#xff0c;就是一道典型的 “看…引言对于初学编程的小伙伴来说LeetCode 中的字符串匹配类题目常常让人头疼 —— 既要处理复杂的字符组合又要兼顾效率很容易陷入 “暴力破解超时” 的困境。今天要讲的第 30 题 “串联所有单词的子串”就是一道典型的 “看似复杂但有巧解” 的题目。它不仅考察对字符串的基本操作还能帮我们入门 “哈希表” 和 “滑动窗口” 这两个编程中超实用的技巧。这两个技巧就像两把钥匙能打开很多字符串、数组类题目的大门学会后会发现很多难题都能迎刃而解。接下来我们就从题目理解开始一步步拆解思路逐行分析代码让新手也能轻松掌握这道题的解法引言目录一、题目理解到底要找什么二、核心思路哈希表滑动窗口三、代码逐行拆解新手也能看明白关键部分详细解释1. 两个哈希表的作用2. 为什么要分len轮遍历3. 滑动窗口的核心操作进窗口→出窗口→判断四、新手容易踩的坑解决办法五、例子演示帮助理解六、总结解题步骤新手可直接套用目录一、题目理解到底要找什么先把复杂题目变简单题目说给一个字符串s和一个单词数组words数组里所有单词长度都一样我们要找s中这样的子串它刚好是words里所有单词随便排序后拼接起来的最后返回这些子串的开始索引顺序无所谓举个例子就明白如果words [foo,bar]那拼接后的可能是barfoo或foobar只要s里有这两个子串它们的起始位置就要返回。关键规律每个单词长度是lenwords有m个单词所以目标子串长度一定是len * m比如上面的3*26只要子串长度不对直接排除不用浪费时间判断二、核心思路哈希表滑动窗口这道题的核心是用「哈希表记频次」「滑动窗口找符合条件的子串」新手可以这么理解哈希表就像一个计数器先记下words里每个单词出现了几次比如[foo,bar]就是foo:1bar:1滑动窗口就像一个可移动的“框”在s里框出一段长度为len*m的子串看看这个框里的单词是不是刚好和words里的单词完全匹配数量和种类都一致为什么要这么做如果暴力遍历所有可能的子串再拆分单词对比会特别慢比如s很长、words很多的时候哈希表查频次很快滑动窗口能重复利用之前的判断结果效率大大提高三、代码逐行拆解新手也能看明白先看完整代码已加详细注释classSolution{public:vectorintfindSubstring(string s,vectorstringwords){// 哈希表1记录words中所有单词的频次比如[foo,bar]就是foo:1bar:1unordered_mapstring,inthash1;for(autoword:words)hash1[word];// 遍历words给每个单词计数vectorintret;// 用来存最终找到的起始索引intlenwords[0].size();// 每个单词的长度题目说所有单词长度相同intmwords.size();// words数组的单词个数inttotal_lenlen*m;// 目标子串的总长度必须是这个长度才有可能符合条件// 关键循环1按单词长度分轮遍历比如单词长3就分0、1、2三个起始位置开始for(inti0;ilen;i){unordered_mapstring,inthash2;// 哈希表2记录当前窗口里的单词频次// 滑动窗口的三个关键变量left窗口左边界、right窗口右边界、count匹配上的单词个数for(intlefti,righti,count0;rightlens.size();rightlen){// 1. 把当前right位置的单词加入窗口进窗口string in_words.substr(right,len);// 从right开始取len个字符作为当前单词hash2[in_word];// 给这个单词的频次1// 2. 维护count如果当前单词在words里且窗口里的频次没超过words里的频次说明匹配上一个if(hash2[in_word]hash1[in_word]){count;}// 3. 窗口长度超过目标长度了需要把左边的单词移出窗口出窗口if(right-left1total_len){string out_words.substr(left,len);// 要移出的左边单词// 如果移出的单词是words里的且移出前的频次没超过words里的频次说明匹配数要减1if(hash2[out_word]hash1[out_word]){count--;}hash2[out_word]--;// 移出单词频次-1leftlen;// 左边界右移窗口缩小}// 4. 如果匹配上的单词个数等于words的长度说明当前窗口是符合条件的子串if(countm){ret.push_back(left);// 记录左边界起始索引}}}returnret;// 返回所有找到的起始索引}};关键部分详细解释1. 两个哈希表的作用hash1全局计数器记录words中每个单词必须出现的次数比如words [bar,foo,the]就是bar:1、foo:1、the:1hash2窗口计数器记录当前滑动窗口中每个单词出现的次数比如窗口里是foo,“bar”,“the”就是foo:1、bar:1、the:12. 为什么要分len轮遍历比如单词长度是3len3我们要考虑三种起始位置第0轮从索引0、3、6…开始取单词0→3→6→…第1轮从索引1、4、7…开始取单词1→4→7→…第2轮从索引2、5、8…开始取单词2→5→8→…这样做是为了不遗漏任何可能的子串因为目标子串是由完整单词拼接的所以起始位置一定是这len种情况之一。3. 滑动窗口的核心操作进窗口→出窗口→判断进窗口把右边的单词加入hash2如果这个单词是words里的且没超量就给匹配数count1出窗口如果窗口太长超过total_len就把左边的单词移出hash2如果这个单词是words里的且移出前没超量就给count-1判断如果count m匹配数等于words的单词个数说明当前窗口刚好是符合条件的子串记录左边界四、新手容易踩的坑解决办法忘记单词长度相同的条件题目明确说words中所有字符串长度相同所以可以直接用words[0].size()不用考虑每个单词长度不一样的情况窗口长度计算错误窗口长度是right - left 1目标长度是len * m当窗口超过这个长度时必须移出左边的单词count的维护逻辑只有当单词在words里且频次没超量时才增减count否则不管比如s里的单词不在words里加入或移出都不影响count哈希表的使用unordered_map的键是字符串单词值是频次新手要注意substr的用法substr(起始索引, 长度)五、例子演示帮助理解以示例1为例s barfoothefoobarmanwords [foo,bar]len3m2total_len6第0轮遍历i0left0right0进窗口barhash2[bar]1count1因为hash1[bar]1right3进窗口foohash2[foo]1count2此时count m记录left0第一个答案right6进窗口the窗口长度76移出左边barhash2[bar]0count1… 继续滑动直到right9right9进窗口foohash2[foo]1count1right12进窗口barhash2[bar]1count2记录left9第二个答案最终返回[0,9]和示例结果一致六、总结解题步骤新手可直接套用计算单词长度len、单词个数m、目标子串长度total_len len * m用hash1记录words中每个单词的频次按len轮遍历起始位置0到len-1初始化窗口变量left、right、count和hash2滑动窗口每次右移len个位置取一个完整单词进窗口更新hash2和count出窗口如果窗口超长更新hash2和count判断如果count m记录left返回所有记录的起始索引这种方法的效率很高适合处理题目中的数据规模s长度1e4words长度5000新手掌握后遇到类似的字符串匹配问题都可以用「哈希表滑动窗口」的思路来解决