抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

LeetCode-Hot100-子串

leetcode

发布于：2024年10月9日

字数：1.8k 字

时长：8 分钟

前言

题单LeetCode 热题 100的子串部分，给出解析。

560. Subarray Sum Equals K

原题链接

题目描述

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

1
2
Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

1
2
Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

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

解题方法

要解决这个问题，我们可以使用前缀和（prefix sum）和哈希表来有效地计算满足条件的子数组数量。以下是解题思路：

  1. 定义前缀和：计算从数组起始位置到当前位置的和。
  2. 使用哈希表：存储每个前缀和出现的次数。
  3. 遍历数组：对每个元素更新前缀和，同时检查是否存在一个前缀和使得当前前缀和减去该前缀和等于 k。如果存在，就可以确定有多少个子数组的和为 k。
  4. 更新哈希表：每次更新前缀和后，将其记录到哈希表中。

代码实现

Python版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        prefix_sum = 0
        prefix_counts = {0: 1}  # 初始化，前缀和为0的次数为1
        
        for num in nums:
            prefix_sum += num
            
            # 检查是否存在一个前缀和，使得 prefix_sum - k 在哈希表中
            if prefix_sum - k in prefix_counts:
                count += prefix_counts[prefix_sum - k]
            
            # 更新哈希表
            if prefix_sum in prefix_counts:
                prefix_counts[prefix_sum] += 1
            else:
                prefix_counts[prefix_sum] = 1
        
        return count

Java版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int prefixSum = 0;
        Map<Integer, Integer> prefixCounts = new HashMap<>();
        prefixCounts.put(0, 1);  // 初始化，前缀和为0的次数为1

        for (int num : nums) {
            prefixSum += num;

            // 检查是否存在一个前缀和，使得 prefix_sum - k 在哈希表中
            if (prefixCounts.containsKey(prefixSum - k)) {
                count += prefixCounts.get(prefixSum - k);
            }

            // 更新哈希表
            prefixCounts.put(prefixSum, prefixCounts.getOrDefault(prefixSum, 0) + 1);
        }

        return count;
    }
}

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(n)$

239. Sliding Window Maximum

原题链接

题目描述

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Constraints:

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

解题方法

这个问题可以使用双端队列（deque）来高效求解。

遍历数组，将数在数组中的下标存放在双端队列中，并且双端队列中存放的对应的数是从大到小排序。如果当前遍历到的数比队尾索引对应的值大，则移除所有小于当前遍历到的数的索引。当遍历下标达到一个窗口的大小时，记录窗口中的最大值并移除不在窗口内的索引。

代码实现

Python版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return []
        
        result = []
        deq = deque()  # 存储索引

        for i in range(len(nums)):
            # 移除不在窗口内的索引
            if deq and deq[0] < i - k + 1:
                deq.popleft()
            
            # 移除小于当前元素的索引
            while deq and nums[deq[-1]] < nums[i]:
                deq.pop()
            
            deq.append(i)
            
            # 从窗口的第一个完整位置开始，记录最大值
            if i >= k - 1:
                result.append(nums[deq[0]])

        return result

Java版本：

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
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }

        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            // 移除不在滑动窗口内的元素
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // 移除所有小于当前元素的索引
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            // 添加当前元素的索引
            deque.offerLast(i);

            // 当窗口大小达到 k 时，记录最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(min(k,U))$，其中 $U$ 是 $nums$ 中不同元素的个数。双端队列至多有 $k$ 个元素。

76. Minimum Window Substring

原题链接

题目描述

Given two strings s and t of lengths m and n respectively, return _the minimum window substring_ of s such that every character in t ( including duplicates ) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique .

Example 1: 

1
2
3
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2: 

1
2
3
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3: 

1
2
3
4
Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 10^5
  • s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

解题方法

题目要求在 s 字符串中找到能够涵盖 t 所有字符的最小子串，使用「滑动窗口」算法解决这个问题。

  1. 维护两个计数器，分别记录字符串 t 中每个字符的需求数和窗口中的字符数。
  2. 使用左右指针表示窗口的范围，首先将右指针右移，以便扩大窗口，直到包含了 t 所有字符。
  3. 当窗口已经包含了 t 所有字符后，开始移动左指针缩小窗口，以寻找可能更短的子串。
  4. 每次窗口包含了 t 所有字符时，更新最小子串的起始位置和长度。
  5. 如果没有找到满足条件的子串，返回空字符串，否则返回找到的最小子串。

代码实现

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
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = {}
        for char in t:
            need[char] = need.get(char, 0) + 1  # 初始化需求表

        window = {}
        left, right = 0, 0
        valid = 0  # 满足需求的字符数量
        start, length = 0, float("inf")  # 记录最小子串的起始位置和长度

        while right < len(s):
            # 即将移入窗口的字符
            c = s[right]
            right += 1
            # 更新窗口内的字符记录
            if c in need:
                window[c] = window.get(c, 0) + 1
                if window[c] == need[c]:  # 当前字符的数量满足需求
                    valid += 1

            # 判断左侧窗口是否需要收缩
            while valid == len(need):
                # 更新最小覆盖子串
                if right - left < length:
                    start = left
                    length = right - left

                # d 是将移出窗口的字符
                d = s[left]
                left += 1
                # 更新窗口内的字符记录
                if d in need:
                    if window[d] == need[d]:  # 当前字符数量不再满足需求
                        valid -= 1
                    window[d] -= 1  # 减少窗口中该字符的数量

        # 返回最小子串，如果没找到返回空字符串
        return s[start : start + length] if length != float("inf") else ""

复杂度分析

时间复杂度：$O(m+n)$，其中 $m$ 是字符串 $s$ 的长度，$n$ 是字符串 $t$ 的长度。

空间复杂度：$O(k)$，其中 $k$ 是字符串 $t$ 中不同字符的数量。

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://blog.skyheart.moe/posts/5a6eb32a/

更新于：2024年10月30日

子串

评论