网站开发 怎样做费用结算软文推广广告公司

题目

链接：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);}