外包网易_建设企业网站报价_软件外包公司_it培训机构哪个好

在力扣（LeetCode）平台上，热题 100 是许多开发者提升算法能力的必刷清单。今天，我们就来详细解析热题 100 中与子串相关的三道题，帮助大家更好地理解解题思路和技巧。

一、和为 K 的子数组

1. 题目描述

给定一个整数数组 nums 和一个整数 k，找到和为 k 的子数组的个数。

2. 示例

示例 1：

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

输出：2

解释：和为 2 的子数组有 [1, 1] 和 [1, 1]。

3. 解题思路

这道题主要考察前缀和和哈希表的应用。我们可以使用前缀和来计算子数组的和，使用哈希表来存储前缀和出现的次数。具体步骤如下：

1. 初始化前缀和 sum 为 0，哈希表 map 用于存储前缀和出现的次数，初始时 map[0] = 1。
2. 遍历数组，对于每个元素 nums[i]，更新前缀和 sum。
3. 检查 sum - k 是否在哈希表中存在，如果存在，则说明存在和为 k 的子数组，更新结果计数。
4. 更新哈希表中 sum 的出现次数。

4. 代码实现（Java）

import java.util.HashMap;public class Solution {public int subarraySum(int[] nums, int k) {HashMap<Integer, Integer> map = new HashMap<>();map.put(0, 1);int sum = 0, count = 0;for (int num : nums) {sum += num;if (map.containsKey(sum - k)) {count += map.get(sum - k);}map.put(sum, map.getOrDefault(sum, 0) + 1);}return count;}
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次，每次哈希表的查找和插入操作都是 O(1)。
• 空间复杂度 ：O(n)，需要使用哈希表存储前缀和及其出现次数。

二、滑动窗口最大值

1. 题目描述

给定一个数组 nums 和一个滑动窗口的大小 k，找到每个滑动窗口中的最大值。

2. 示例

示例 1：

输入：nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

输出：[3, 3, 5, 5, 6, 7]

解释：滑动窗口中的最大值分别为 3、3、5、5、6、7。

3. 解题思路

这道题主要考察双端队列的应用。我们可以使用双端队列来维护滑动窗口中的最大值。具体步骤如下：

1. 初始化双端队列 deque，用于存储数组元素的索引。
2. 遍历数组，对于每个元素 nums[i]：
   • 移除双端队列中索引小于 i - k + 1 的元素，因为这些元素已经不在滑动窗口中。
   • 移除双端队列中值小于 nums[i] 的元素，因为这些元素不可能是滑动窗口中的最大值。
   • 将当前元素的索引 i 添加到双端队列的末尾。
   • 如果滑动窗口已经形成（即 i >= k - 1），记录当前滑动窗口的最大值 nums[deque[0]]。

4. 代码实现（Java）

import java.util.ArrayDeque;
import java.util.Deque;public class Solution {public int[] maxSlidingWindow(int[] nums, int k) {Deque<Integer> deque = new ArrayDeque<>();int[] result = new int[nums.length - k + 1];for (int i = 0; i < nums.length; i++) {while (!deque.isEmpty() && deque.peek() < i - k + 1) {deque.poll();}while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {deque.pollLast();}deque.offer(i);if (i >= k - 1) {result[i - k + 1] = nums[deque.peek()];}}return result;}
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次，每次双端队列的操作都是 O(1)。
• 空间复杂度 ：O(k)，需要使用双端队列存储滑动窗口中的元素索引。

三、最小覆盖子串

1. 题目描述

给定两个字符串 s 和 t，找到 s 中包含 t 中所有字符的最小子串。

2. 示例

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"

输出："BANC"

解释：最小子串是 "BANC"，包含 t 中的所有字符。

3. 解题思路

这道题主要考察滑动窗口的应用。我们可以使用滑动窗口来维护一个包含 t 中所有字符的子串。具体步骤如下：

1. 初始化两个指针 left 和 right，分别表示滑动窗口的左右边界。
2. 使用两个数组 window 和 target 来存储当前窗口内的字符计数和目标字符串的字符计数。
3. 遍历字符串 s，对于每个字符 s[right]：
   • 更新当前窗口内的字符计数 window。
   • 如果当前窗口包含 t 中的所有字符，尝试移动 left 指针来缩小窗口大小。
   • 记录最小窗口的起始索引和长度。
4. 重复步骤 3，直到 right 遍历完整个字符串。

4. 代码实现（Java）

public class Solution {public String minWindow(String s, String t) {int[] window = new int[128];int[] target = new int[128];for (char c : t.toCharArray()) {target[c]++;}int left = 0, right = 0, formed = 0, minLen = Integer.MAX_VALUE, minStart = 0;int required = t.length();while (right < s.length()) {char c = s.charAt(right);window[c]++;if (target[c] > 0 && window[c] == target[c]) {formed++;}while (left <= right && formed == required) {c = s.charAt(left);if (right - left + 1 < minLen) {minLen = right - left + 1;minStart = left;}window[c]--;if (target[c] > 0 && window[c] < target[c]) {formed--;}left++;}right++;}return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);}
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是字符串 s 的长度。我们只需要遍历字符串一次，每次移动指针的时间复杂度都是 O(1)。
• 空间复杂度 ：O(1)，我们只使用了固定大小的数组来存储字符计数。

以上就是力扣热题 100 中与子串相关的三道题的详细解析，希望对大家有所帮助。在实际刷题过程中，建议大家多动手实践，理解解题思路的本质，这样才能更好地应对各种算法问题。