网站建设基础流程,箱包商城网站建设,用c 做网站可以吗,佛山网站建设公司大全题目
链接#xff1a;leetcode链接
思路分析#xff08;滑动窗口#xff09;
还是老样子#xff0c;连续问题#xff0c;滑动窗口哈希表
令t用的hash表为hash1#xff0c;s用的hash表为hash2
利用hash表统计窗口内的个字符出现的个数#xff0c;与hash1进行比较 选…题目
链接leetcode链接
思路分析滑动窗口
还是老样子连续问题滑动窗口哈希表
令t用的hash表为hash1s用的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);}
