《LeetCode热题100》---＜4.子串篇三道＞

本篇博客讲解LeetCode热题100道子串篇中的三道题

第一道：和为 K 的子数组

第二道：滑动窗口最大值

第三道：最小覆盖子串

第一道：和为 K 的子数组（中等）

法一：暴力枚举

 class Solution {public int subarraySum(int[] nums, int target) {int count = 0;for (int start = 0; start < nums.length; ++start) {int sum = 0;for (int end = start; end >= 0; --end) {sum += nums[end];if (sum == target) {count++;}}}return count;}
}

思想比较简单，找到所有子数组的和，如果等于目标值target。那么count++

最终返回count

法二：前缀和 + 哈希表优化

class Solution {public int subarraySum(int[] nums, int target) {int count = 0, pre = 0;HashMap < Integer, Integer > map = new HashMap < > ();map.put(0, 1);for (int i = 0; i < nums.length; i++) {pre += nums[i];if (map.containsKey(pre - target)) {count += map.get(pre - target);}map.put(pre, map.getOrDefault(pre, 0) + 1);}return count;}
}

前缀和：是求解子数组的和等问题的好方法。通过累加数组中的值，使其减去数组中某个值来得到子数组的和。 

前缀和用法示例: 

 

建哈希表优化后。 

 

前缀和： 使用pre += nums[i]; 用pre变量来累加前缀和。只需要pre即可。

因为我们只需要用累加和减去目标值target。再去哈希表中找有没有对应的值。

如果有对应的值，说明存在子数组的和为target。那么count++

最终返回conunt

第二道：滑动窗口最大值（困难）

法一：优先队列

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;PriorityQueue<int[]> pQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {public int compare(int[] pair1, int[] pair2) {return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];}});for (int i = 0; i < k; ++i) {pQueue.offer(new int[]{nums[i], i});}int[] ans = new int[n - k + 1];ans[0] = pQueue.peek()[0];for (int i = k; i < n; ++i) {pQueue.offer(new int[]{nums[i], i});while (pQueue.peek()[1] <= i - k) {pQueue.poll();}ans[i - k + 1] = pQueue.peek()[0];}return ans;}
}

1. 定义一个优先队列（最大堆）pQueue，用于存储滑动窗口内的元素。队列按照元素值降序排列，如果值相同则按索引降序排列。
2. 初始化队列，将数组前 k 个元素加入队列。
3. 创建结果数组 ans，用于存储每个窗口的最大值。
4. 将队列顶部（最大值）的元素值存入结果数组的第一个位置。
5. 从第 k 个元素开始，逐步将元素加入队列，并移除不在当前滑动窗口内的元素（根据索引判断）。
6. 每次移动窗口后，将当前窗口的最大值（队列顶部元素值）存入结果数组相应位置。
7. 最终返回结果数组。

 使用优先队列高效地计算了数组中每个滑动窗口的最大值。

 法二：单调队列（单调性的双端队列）

单调队列套路

• 入（元素进入队尾，同时维护队列单调性）
• 出（元素离开队首）
• 记录/维护答案（根据队首）

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;Deque<Integer> deque = new LinkedList<Integer>();for (int i = 0; i < k; ++i) {while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {deque.pollLast();}deque.offerLast(i);}int[] ans = new int[n - k + 1];ans[0] = nums[deque.peekFirst()];for (int i = k; i < n; ++i) {while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {deque.pollLast();}deque.offerLast(i);while (deque.peekFirst() <= i - k) {deque.pollFirst();}ans[i - k + 1] = nums[deque.peekFirst()];}return ans;}
}

1. 初始化一个双端队列，用于存储数组元素的索引。
2. 遍历数组前 k 个元素，保持队列中元素对应的数组值按降序排列，并存储这些元素的索引。
3. 初始化结果数组 ans 并将第一个窗口的最大值（队列头部的元素）存入 ans 的第一个位置。
4. 遍历数组剩余元素：

• 将新的元素索引加入队列，并移除队列中所有比当前元素小的元素的索引。
• 移除队列中不在当前窗口范围内的索引。
• 将当前窗口的最大值（队列头部的元素）存入 ans 的相应位置。

最终返回结果数组 ans。

法三：分块 + 预处理

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;int[] prefixMax = new int[n];int[] suffixMax = new int[n];for (int i = 0; i < n; ++i) {if (i % k == 0) {prefixMax[i] = nums[i];}else {prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);}}for (int i = n - 1; i >= 0; --i) {if (i == n - 1 || (i + 1) % k == 0) {suffixMax[i] = nums[i];} else {suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);}}int[] ans = new int[n - k + 1];for (int i = 0; i <= n - k; ++i) {ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);}return ans;}
}

 

• 初始化前缀最大值和后缀最大值数组：

  • prefixMax[i] 表示从块的开始到索引 i 的最大值。
  • suffixMax[i] 表示从索引 i 到块的结束的最大值。

• 构建前缀最大值数组：

  • 遍历数组，如果索引 i 是块的开始，prefixMax[i] 等于 nums[i]。
  • 否则，prefixMax[i] 等于 prefixMax[i - 1] 和 nums[i] 的最大值。

• 构建后缀最大值数组：

  • 从数组末尾遍历，如果索引 i 是块的结束，suffixMax[i] 等于 nums[i]。
  • 否则，suffixMax[i] 等于 suffixMax[i + 1] 和 nums[i] 的最大值。

• 计算每个滑动窗口的最大值：

  • 遍历 ans 数组，每个窗口的最大值是 suffixMax[i] 和 prefixMax[i + k - 1] 的最大值。

• 返回结果数组：

  • 返回存有每个滑动窗口最大值的结果数组 ans

第三道：最小覆盖子串（困难）

 

方法一：滑动窗口 

 

class Solution {Map<Character, Integer> ori = new HashMap<Character, Integer>();Map<Character, Integer> cnt = new HashMap<Character, Integer>();public String minWindow(String s, String t) {int tLen = t.length();for (int i = 0; i < tLen; i++) {char c = t.charAt(i);ori.put(c, ori.getOrDefault(c, 0) + 1);}int l = 0, r = -1;int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;int sLen = s.length();while (r < sLen) {++r;if (r < sLen && ori.containsKey(s.charAt(r))) {cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);}while (check() && l <= r) {if (r - l + 1 < len) {len = r - l + 1;ansL = l;ansR = l + len;}if (ori.containsKey(s.charAt(l))) {cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);}++l;}}return ansL == -1 ? "" : s.substring(ansL, ansR);}public boolean check() {Iterator iter = ori.entrySet().iterator(); while (iter.hasNext()) { Map.Entry entry = (Map.Entry) iter.next(); Character key = (Character) entry.getKey(); Integer val = (Integer) entry.getValue(); if (cnt.getOrDefault(key, 0) < val) {return false;}} return true;}
}

• 初始化哈希表：

  • 使用 ori 哈希表记录字符串 t 中每个字符出现的次数。
  • 使用 cnt 哈希表记录当前窗口中每个字符的出现次数。

• 滑动窗口的初始化：

  • 初始化左指针 l 和右指针 r，分别表示当前窗口的左右边界。
  • 初始化记录最小窗口长度的 len 和最小窗口的起始和结束位置 ansL 和 ansR。

• 滑动窗口扩展：

  • 移动右指针扩展窗口，若当前字符在 t 中，将其加入 cnt。

• 缩小窗口：

  • 当窗口内包含了 t 中所有字符时，尝试缩小窗口：
    • 如果当前窗口长度小于已记录的最小窗口长度，更新最小窗口的位置和长度。
    • 移动左指针，若左指针指向的字符在 t 中，将其从 cnt 中移除。

• 返回结果：

  • 如果找到了符合条件的窗口，返回最小窗口的子字符串，否则返回空字符串。

• 辅助方法 check：

  • 检查当前窗口是否包含 t 中所有字符，即 cnt 中每个字符的数量是否都不小于 ori 中对应的数量。