当前位置: 首页> 教育> 就业 > 幼儿园主题网络图设计美丽鹭岛_公司网站建设_产品推广活动策划方案_营销培训课程视频

幼儿园主题网络图设计美丽鹭岛_公司网站建设_产品推广活动策划方案_营销培训课程视频

时间:2025/7/11 23:09:32来源:https://blog.csdn.net/2303_78940834/article/details/142306015 浏览次数:0次
幼儿园主题网络图设计美丽鹭岛_公司网站建设_产品推广活动策划方案_营销培训课程视频

题目

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

思路分析(滑动窗口)

还是老样子,连续问题,滑动窗口+哈希表

令t用的hash表为hash1,s用的hash表为hash2

利用hash表统计窗口内的个字符出现的个数,与hash1进行比较
选取符合情况的最小子串即可。

问题来了,该题目需要大量使用hash表比较,这是时间复杂度很高的,并不是和好,怎么去优化呢?

还是利用一个变量count去统计有效元素
详情见异位词的那道题
传送们:438.找到字符串中所有字母异位词

注意,这里有一点比较坑

这道题,最后要求我们返回的是子串,而不是下标,
一定要设置一个begin和len来标记子串,
而不要在过程中,每一次更新结果的时候都创建一个子串
不然内存会溢出,
样例里面有内存特别大的极端样例

代码

string minWindow(string s, string t) {int hash1[128] = {0};int hash2[128] = {0};for(auto& s:t) hash1[s]++;int count = 0;int len = INT_MAX,begin = -1;for(int left = 0,right = 0;right < s.size();++right){char in = s[right];hash2[in]++;//进窗口if(hash2[in] <= hash1[in])count++;while(count >= t.size()){if(right - left + 1 < len){len = right - left + 1;begin = left;}char out = s[left];if(hash2[out] <= hash1[out]) count--;hash2[out]--;left++;}}if(begin == -1)return "";return s.substr(begin,len);}
关键字:幼儿园主题网络图设计美丽鹭岛_公司网站建设_产品推广活动策划方案_营销培训课程视频

版权声明:

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

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

责任编辑: