LeetCode 热题 100-子串

和为k的子数组

前缀和

数组不是单调的话，不要用滑动窗口，考虑用前缀和。前缀和i到j-1之间为prefix[j] - prefix[i] = k，即prefix[i] = prefix[j] - k，即遍历所有的j，统计prefix[i]出现的次数。

两次遍历做法：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 计算前缀和
        int n = nums.size();
        vector<int>  prefix(n + 1);
        for(int i = 0; i < n; i++){
            prefix[i+1] = prefix[i] + nums[i];
        }
        // 统计次数
        int ans = 0;
        unordered_map<int, int> hash;
        for(int sj : prefix){
            ans += hash.contains(sj - k) ? hash[sj - k] : 0;
            hash[sj]++;
        }
        return ans;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

一次遍历：计算前缀和的同时遍历前缀和。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = 0, prefix = 0;
        // 初始化哈希表
        unordered_map<int, int> hash{{0, 1}};
        // 一边计算前缀和，一边遍历前缀和
        for(int x : nums){
            prefix += x;
            ans += hash.contains(prefix - k) ? hash[prefix - k] : 0;
            hash[prefix]++;
        }
        return ans;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

滑动窗口最大值

双端队列

及时去掉无用数据，保证双端队列有序：

1. 入（元素进入队尾，同时维护队列单调性）
2. 出（元素离开队首）
3. 记录/维护答案（根据队首）

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> que;
        for(int i = 0; i <nums.size(); i++){
            // 入
            while(!que.empty() && nums[que.back()] <= nums[i]){
                que.pop_back();
            }
            que.push_back(i);
            // 出
            if(i - que.front() + 1 > k){
                que.pop_front();
            }
            // 记录答案
            if(i >= k-1){
                ans.push_back(nums[que.front()]);
            }
        }
        return ans;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(min(k,U))，其中 U 是 nums 中的不同元素个数（本题至多为 20001）.

最小覆盖子串

滑动窗口

维护一个s的窗口子串，如果它涵盖t中所有字符，就将左指针右移，即将最左边的元素移出窗口。判断涵盖t可以使用两个数组分别统计当前s和t的字符数情况，然后每次逐个字符判断，这样每次都要花费 O(∣Σ∣) 的时间去判断是否涵盖。因此可以用一个变量less代替，即目前子串中有 less 种字母的出现次数小于 t 中字母的出现次数。

1. 初始化左右指针。
2. 用一个哈希表统计t的字符情况。
3. 初始化left，并用一个哈希表统计s的情况。
4. 初始化 less 为 t 中的不同字母个数。
5. 遍历 s，设当前枚举的子串右端点为 right，把字母 c=s[right] 的出现次数加一。加一后，如果 cntS[c]=cntT[c]，说明 c 的出现次数满足要求，把 less 减一。
6. 如果 less=0，说明 cntS 中的每个字母及其出现次数都大于等于 cntT 中的字母出现次数，那么：
   • 更新最短子串长度；
   • 滑动窗口左边界右移，更新cntS和less。
   • 重复上述步骤直至less>0.
7. 如果 ansLeft<0，说明没有找到符合要求的子串，返回空字符串，否则返回下标 ansLeft 到下标 ansRight 之间的子串。

可以把 cntS 和 cntT 合并成一个 cnt，定义cnt[x]=cntT[x]−cntS[x]。

class Solution {
public:
    string minWindow(string s, string t) {
        int m = s.length();
        int n = t.length();
        int ansLeft = -1, ansRight = m;
        int cnt[128]{};
        int less = 0;
        for(char c : t){
            if(cnt[c] == 0){
                less++;
            }
            cnt[c]++;
        }

        // 滑动窗口
        int left = 0;
        for(int right = 0; right < m; right++){
            char c = s[right];
            cnt[c]--;
            if(cnt[c] == 0){
                less--;
            }

            // 窗口子串涵盖t，不断更新长度
            while(less == 0){
                if(right - left < ansRight - ansLeft){
                    ansLeft = left;
                    ansRight = right;
                }
                char x = s[left];   // 左端点
                if(cnt[x] == 0){
                    less++;         // 移出之后不一样的字母会多
                }
                cnt[x]++;
                left++;
            }
        }
        return ansLeft < 0 ? "" : s.substr(ansLeft, ansRight - ansLeft + 1);
    }
};

• 时间复杂度：O(m+n)
• 空间复杂度：O(∣Σ∣)