LeetCode Hot 100 (4) 子串

小帅 1/5/2024 LeetCode

# 560. 和为 K 的子数组 (opens new window)

题目：

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

1
2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

1
2

提示：

1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7

思路：

前缀和+哈希表在遍历求前缀和的同时记录以每个数结尾的前缀和值作为key，出现的数目作为value，然后通过哈希表求哈希表中有没有数能满足当前的位置的前缀和减去哈希表中的key等于目标值，满足的话将value加入到结果中。

代码：

C++代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        int pre_sum = 0;
        int res = 0;
        mp[0] = 1;
        for(int i=0;i<nums.size();i++) {
            pre_sum += nums[i];
            if(mp.count(pre_sum-k)==1) {
                res += mp[pre_sum-k];
            }
            mp[pre_sum]++;
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Go代码

func subarraySum(nums []int, k int) int {
    mp := make(map[int]int)
    res := 0
    mp[0] = 1
    pre_sum := 0
    for i:= 0;i<len(nums);i++ {
        pre_sum += nums[i]
        v, ok := mp[pre_sum-k]
        if ok {
            res += v
        }
        mp[pre_sum]++
    }
    return res
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 239. 滑动窗口最大值 (opens new window)

题目：

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

1
2
3
4
5
6
7
8
9
10
11

示例 2：

输入：nums = [1], k = 1
输出：[1]

1
2

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

思路：

单调队列模板题维护一个单调递减的队列，遍历过程中如果队列头部有是应该被挤出队列的坐标，那么把它挤出去，然后从尾部开始如果队尾坐标的值小于等于当前位置的值那么将其出队尾，那么每次对头即为当前最大元素

代码：

C++代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> q(1e5);
        int hh = 0, tt = -1;
        vector<int> res;
        for(int i=0;i<nums.size();i++) {
            if(tt>=hh&&q[hh]<i-k+1) hh++;
            while(tt>=hh&&nums[i]>=nums[q[tt]]) tt--;
            q[++tt] = i;
            if(i>=k-1) res.push_back(nums[q[hh]]);
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Go代码

func maxSlidingWindow(nums []int, k int) []int {
    q := make([]int,1e5)
    res := make([]int,0)
    hh , tt := 0, -1
    for i:=0;i<len(nums);i++ {
        if tt>=hh&&q[hh]<i-k+1 {
            hh++
        }
        for tt>=hh&&nums[i]>=nums[q[tt]] {
            tt--
        }
        tt++
        q[tt] = i
        if i>=k-1 {
            res = append(res,nums[q[hh]])
        }
    }
    return res
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 76. 最小覆盖子串 (opens new window)

题目：

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

1
2
3

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

1
2
3

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

1
2
3
4

提示：

m == s.length
n == t.length
1 <= m, n <= 10^5
s 和 t 由英文字母组成

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

思路：

双指针+哈希表用一个哈希表表示t，t的每个字符作为key，数量作为value。在遍历s的过程中，如果遍历到的数是一个有用的字符，计数器加一，当计数器加到和字符串t长度相同时可能就是一个有效的答案。

代码：

C++代码

class Solution {
public:
string minWindow(string s, string t) {
    unordered_map<char,int> mp1,mp2;
    for(char c:t) {
        mp2[c]++;
    }
    string res = "";
    int cnt = 0;
    for(int i=0,j=0;i<s.size();i++) {
        mp1[s[i]]++;
        if(mp1[s[i]]<=mp2[s[i]]) {
            cnt++;
        }
        while(j<=s.size()&&mp1[s[j]]>mp2[s[j]]) {
            mp1[s[j]]--;
            j++;
        }
        if(cnt==t.size()) {
            if(res.empty()||i-j+1<res.size()) {
                res = s.substr(j,i-j+1);
            }
        }
    }
    return res;
}
};

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

Go代码

func minWindow(s string, t string) string {
    mp1 := make(map[byte]int)
    mp2 := make(map[byte]int)
    for i:=0;i<len(t);i++ {
        mp2[t[i]]++
    }
    cnt := 0
    res := ""
    for i,j:=0,0;i<len(s);i++ {
        mp1[s[i]]++
        if mp1[s[i]]<=mp2[s[i]] {
            cnt++
        }
        for j<len(s)&&mp1[s[j]]>mp2[s[j]] {
            mp1[s[j]]--
            j++
        }
        if cnt == len(t) {
            if(res==""||i-j+1<len(res)) {
                res = s[j:i+1]
            }
        }
    }
    return res
}

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

小帅的博客

Choose mode