当前位置：首页 > article >正文

算法：76.最小覆盖子串

article 2024/9/22 21:04:58

题目

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

查看全文

http://www.kler.cn/news/308346.html