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

力扣hot100——子串

article 2025/1/31 11:00:26

560. 和为 K 的子数组

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int s = 0;
        map<int, int> mp;
        mp[0]++;
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            s += nums[i];
            ans += mp[s - k];
            mp[s]++;
        }
        return ans;
    }
};

前缀和哈希

239. 滑动窗口最大值

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& a, int k) {
        deque<int> dq;
        int n = a.size();
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            while (dq.size() && i - dq.front() + 1 > k) dq.pop_front();
            while (dq.size() && a[i] >= a[dq.back()]) dq.pop_back();
            dq.push_back(i);
            if (i >= k - 1) ans.push_back(a[dq.front()]);
        }
        return ans;
    }
};

单调队列板子题

76. 最小覆盖子串

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hs;
        unordered_map<char, int> ht;
        int n = s.size(), m = t.size();
        for (int i = 0; i < m; i++) {
            ht[t[i]]++;
        }

        string ans = "";
        /*
            i是快指针，j是慢指针
            [j, i]
        */
        for (int i = 0, j = 0, cnt = 0; i < n; i++) {
            hs[s[i]]++;
            if (hs[s[i]] <= ht[s[i]]) cnt++;
            while (hs[s[j]] > ht[s[j]]) {
                hs[s[j]]--;
                j++;
            }
            if (cnt == m) {
                if (ans.empty() || ans.size() > i - j + 1) {
                    ans = s.substr(j, i - j + 1);
                }
            }
        }
        return ans;
    }
};