《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;}
}
- 定义一个优先队列（最大堆）
pQueue，用于存储滑动窗口内的元素。队列按照元素值降序排列，如果值相同则按索引降序排列。- 初始化队列，将数组前
k个元素加入队列。- 创建结果数组
ans，用于存储每个窗口的最大值。- 将队列顶部（最大值）的元素值存入结果数组的第一个位置。
- 从第
k个元素开始，逐步将元素加入队列，并移除不在当前滑动窗口内的元素（根据索引判断）。- 每次移动窗口后，将当前窗口的最大值（队列顶部元素值）存入结果数组相应位置。
- 最终返回结果数组。
使用优先队列高效地计算了数组中每个滑动窗口的最大值。
法二：单调队列（单调性的双端队列）
单调队列套路
- 入（元素进入队尾，同时维护队列单调性）
- 出（元素离开队首）
- 记录/维护答案（根据队首）
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;}
}
- 初始化一个双端队列，用于存储数组元素的索引。
- 遍历数组前
k个元素，保持队列中元素对应的数组值按降序排列，并存储这些元素的索引。- 初始化结果数组
ans并将第一个窗口的最大值（队列头部的元素）存入ans的第一个位置。- 遍历数组剩余元素：
- 将新的元素索引加入队列，并移除队列中所有比当前元素小的元素的索引。
- 移除队列中不在当前窗口范围内的索引。
- 将当前窗口的最大值（队列头部的元素）存入
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中对应的数量。