LeetCode Hot100 子串

Posted on

和为k的子数组

Problem

https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked

Solution

记录前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> prefixSumCount;
        prefixSumCount[0] = 1;

        int prefixSum = 0;
        int ans = 0;
        for (int i = 0; i < nums.size(); i ++)
        {
            prefixSum += nums[i];
            if (prefixSumCount.count(prefixSum-k))
            {
                ans += prefixSumCount[prefixSum-k];
            }
            prefixSumCount[prefixSum] ++;
        }
        return ans;
    }
};

滑动窗口最大值

Problem

https://leetcode.cn/problems/sliding-window-maximum/?envType=study-plan-v2&envId=top-100-liked

Solution

需要用的头尾都可以操作的deque，deque存放可能是滑动窗口中最大值的idx，坐标小于滑动窗口左边界的不可能是候选，从frond移除，值在窗口内但小于右边界的不可能是候选，从back移除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();

        deque<int> candidates;

        for (int i = 0; i < n && i < k; i ++)
        {
            while (!candidates.empty() && nums[i] >= nums[candidates.back()])
            {
                candidates.pop_back();
            }
            candidates.push_back(i);
        }
        vector<int> ans;
        ans.push_back(nums[candidates.front()]);

        for (int r = k; r < n; r ++)
        {
            int l = r - k + 1;

            while (!candidates.empty() && candidates.front() < l)
            {
                candidates.pop_front();
            }

            while (!candidates.empty() && nums[r] >= nums[candidates.back()])
            {
                candidates.pop_back();
            }
            candidates.push_back(r);
            ans.push_back(nums[candidates.front()]);
        }
        return ans;
    }
};

最小覆盖子串

Problem

https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-liked

Solution

统计字符串中字符个数，维护滑动窗口中字符个数，记录符合条件且更短的子串start和len。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:

    bool contain(const vector<int> &sCount, const vector<int> &tCount)
    {
        for (int i = 0; i < sCount.size(); i ++)
        {
            if (sCount[i] < tCount[i])
            {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        int sLen = s.length();
        int tLen = t.length();

        vector<int> tCount(52, 0);
        vector<int> sCount(52, 0);

        auto ch2idx = [](char c) -> int
        {
            return c >= 'a' ? 26 + c - 'a' : c - 'A';
        };

        for (int i = 0; i < tLen; i ++)
        {
            int idx = ch2idx(t[i]);
            tCount[idx] ++;
        }

        int l = 0;
        int minL = -1, minLen = sLen;
        for (int r = 0; r < sLen; r ++)
        {
            sCount[ch2idx(s[r])] ++;
            while (contain(sCount, tCount) && l <= r)
            {
                if (minLen >= (r - l + 1))
                {
                    minL = l;
                    minLen = r - l + 1;
                }
                sCount[ch2idx(s[l])] --;
                l ++;
            }
        }

        return minL == -1 ? "" : s.substr(minL, minLen);
    }
};