当前位置: 首页> 游戏> 游戏 > 中国互联网协会会员_乐陵森司特木业_微信附近人推广引流_天猫店铺申请条件及费用

中国互联网协会会员_乐陵森司特木业_微信附近人推广引流_天猫店铺申请条件及费用

时间:2025/7/12 22:56:24来源:https://blog.csdn.net/2303_78940834/article/details/142305731 浏览次数:0次
中国互联网协会会员_乐陵森司特木业_微信附近人推广引流_天猫店铺申请条件及费用

题目

链接:leetcode链接
在这里插入图片描述

思路分析(滑动窗口)

这道题目类似寻找异位词的题目,我认为是寻找异位词的升级版
传送门:寻找异位词

为什么说像呢?
注意:这道题目中words数组里面的字符串长度都是相同的,不妨令长度为len

我们这么来看这道题目,我们把words数组里面的字符串都看成一个字母,那这个题目不就是让我们去在s字符串中去寻找words数组的异位词吗?

难点在哪里呢?

我们以示例一为例:
s = “barfoothefoobarman”, words = [“foo”,“bar”]
在s中寻找的时候,可能bar一组,也可能arf一组,也可能rfo一组,情况非常多
但是,不要忘记了,words数组里面的字符串长度是相同的,
也就是说s中一共也就只有len中情况,直接走len次滑动窗口就行了。

设置count来统计有效元素
我们只需要去统计滑动窗口中有效元素的个数即可。
依旧是进窗口后维护count,
出窗口前维护count。

当count==words.size(),此时的left即为有效下标。

注意:

该题目为定长滑动窗口,当窗口长度 > word.size()就要出窗口了。
该题目需要走len次滑动窗口

代码

vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string,int> hash1;unordered_map<string,int> hash2;vector<int> v;for(auto& s1:words) hash1[s1]++;int count = 0,len = words[0].size(),size = words.size();for(int i = 0;i < len;++i)//走len次滑动窗口{ hash2.clear();//新的一次滑动窗口要重新初始化一下count = 0;for(int left = i,right = i;right < s.size();right += len){string in = s.substr(right,len);hash2[in]++;//进窗口if(hash1.count(in)&&hash2[in] <= hash1[in]) count++;if((right - left) / len + 1 > size)//出窗口{string out = s.substr(left,len);if(hash1.count(out) && hash2[out] <= hash1[out]) count--;hash2[out]--;left+= len;}if(count == size) v.push_back(left);}}return v;}
关键字:中国互联网协会会员_乐陵森司特木业_微信附近人推广引流_天猫店铺申请条件及费用

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: