子串

字符串原来也是一种数据结构

子串又是什么阴

以后再说…

560.和为k的子数组

解：

前缀和 + 哈希表

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map <int, int> cnt;
        cnt[0] = 1;  // 前缀和为 0 出现 1 次

        int sum = 0;
        int ans = 0;

        for(int x : nums){
            sum += x;
            if(cnt.count(sum - k)){
                ans += cnt[sum - k];
            }
            cnt[sum]++;
        }
        
        return ans;
    }
};

239.滑动窗口最大值

解:

使用双端队列deque维护一个按元素值单调递减的索引队列，队列中仅保留当前窗口内的候选最大值索引，因此队头始终对应滑动窗口的最大值~

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ans;
        for(int i = 0; i < nums.size(); i++) {
            while(!dq.empty() && nums[dq.back()] <= nums[i]) {
                dq.pop_back();
            }
            dq.push_back(i);

            if(!dq.empty() && dq.front() < i - k + 1) {
                dq.pop_front();
            }

            if(i >= k - 1) {
                ans.push_back(nums[dq.front()]);
            }
        }
        return ans;
    }
};

76.最小覆盖子串

我们用滑动窗口在s上移动，右指针负责把字符凑齐，左指针则负责在合法前提下尽量缩短

使用两个哈希表:

• need[c] : 代表字符 c 在 t 中需要的次数

• window[c] : 代表字符 c 在当前窗口中已经出现的次数

并用valid表示当前窗口中已经满足 need 要求的字符的种类数，这样，当valid == need.size()时就说明窗口完全覆盖了t!

我们先记录合法状态下的最优答案，再通过移动左指针允许窗口变非法，之后通过移动右指针再次修复，不断遍历，直至结束

因为要寻找的最小窗口，即最优解，往往产生在约束刚刚被破坏的前一刻，所以刻意的破坏是必要的!

解:

class Solution {
public:
    string minWindow(string s, string t) {
        if(t.size() > s.size()) return "";

        unordered_map<char, int> need, window;
        for(char c : t) need[c]++;

        int left = 0, right = 0;
        int valid = 0;

        int start = 0;
        int len = INT_MAX;

        while(right < s.size()) {
            char c = s[right];
            right++;

            // 扩张窗口
            if(need.count(c)) {
                window[c]++;
                if(window[c] == need[c]) {
                    valid++;
                }
            }

            // 收缩窗口
            while(valid == need.size()) {
                if(right - left < len) {
                    start = left;
                    len = right - left;
                }

                char d = s[left];
                left++;

                if(need.count(d)) {
                    if(window[d] == need[d]) {
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};