LeetCode 热题 100 | 子串

子串基础

• 前缀和：前面的数加在一起等于多少，放进map里，key为和，value为这个和出现的次数。
• 单调队列：单调递增/递减队列，每次加入新元素，比新元素大/小的元素全部弹出。
• 滑动窗口：两层循环，外层循环扩展右边界，内层循环缩减左边界。

560. 和为 K 的子数组

题目讲解：LeetCode
重点：

1. 利用当前和减去k等于前缀和这个条件来快速判断。

思路：

1. preSumMap存储前缀和出现的次数。如果当前和减去k出现在preSumMap前缀和字典中，说明当前子数组满足条件。

复杂度：

• n 是数组长度
• 时间复杂度：O(n)
• 空间复杂度：O(n)

public int subarraySum(int[] nums, int k) {int result = 0;// 重点: 用一个map来记录该和出现的次数Map<Integer, Integer> preSumMap = new HashMap<>();preSumMap.put(0, 1);int curSum = 0;for (int i = 0; i < nums.length; i++) {curSum += nums[i];// 重点: 如果 当前和减去k 所需要的前缀和存在则找到答案if (preSumMap.containsKey(curSum - k)) {result += preSumMap.get(curSum - k);}preSumMap.put(curSum, preSumMap.getOrDefault(curSum, 0) + 1);}return result;
}

239. 滑动窗口最大值

题目讲解：LeetCode
重点：

1. 队尾只要有更年轻（i越靠后）同时还能力更强（数值越大）的，留着其他比它更早入职同时能力却更差的没有什么意义，统统开了；队首的虽然能力最强，但是年龄最大，一旦发现它超过年龄范围（不在滑动窗口的范围内），不用看能力就可以直接开了。

思路：

1. 定义一个单调递减队列。前k个单独处理，然后从index为k的开始遍历，利用单调递减队列来快速获取当前窗口最大值。单调递减队列的pop需要处理过期元素。

复杂度：

• n 是数组长度
• 时间复杂度：O(n)。遍历一遍nums
• 空间复杂度：O(k)。队列最多塞k个元素

class MonotonicQueue {Deque<Integer> monotonicQueue;public MonotonicQueue() {this.monotonicQueue = new LinkedList<>();}public int getMaxValues() {return monotonicQueue.getFirst();}public void pop(int val) {// 检查队列头元素是否为上一个窗口头元素, 如果是弹出, 因为已经过期了if (monotonicQueue.getFirst() == val) monotonicQueue.pollFirst();}public void push(int val) {// 推入新元素, 比新元素小的全部popwhile (!monotonicQueue.isEmpty() && val > monotonicQueue.peekLast()) {monotonicQueue.pollLast();}monotonicQueue.offer(val);}
}public int[] maxSlidingWindow(int[] nums, int k) {if (nums.length == 1) return nums;MonotonicQueue monotonicQueue = new MonotonicQueue();int[] result = new int[nums.length - k + 1];int resultIndex = 0;// 前k个单独处理for (int i = 0; i < k; i++) {monotonicQueue.push(nums[i]);}result[resultIndex] = monotonicQueue.getMaxValues();resultIndex++;// 重点: 利用单调递减队列快速获取当前窗口最大值for (int i = k; i < nums.length; i++) {monotonicQueue.pop(nums[i - k]);monotonicQueue.push(nums[i]);result[resultIndex] = monotonicQueue.getMaxValues();resultIndex++;}return result;
}

76. 最小覆盖子串

题目讲解：LeetCode
重点：

1. 滑动窗口外层循环控制右边界，内层循环控制左边界。利用当前匹配好的字符数量来缩减左边界。

思路：

1. 滑动窗口。外层循环扩展右边界，内层循环缩减左边界。用matchedChars来记录当前匹配好的字符数量。如果matchedChars跟字符串t的长度相同，说明当前滑动窗口子串满足条件，开始缩减左边界。如果左边界缩过头就返回到外层循环继续拓展右边界了。

复杂度：

• n 是字符串s的长度
• 时间复杂度：O(n)
• 空间复杂度：O(1)

public String minWindow(String s, String t) {if (s.equals(t)) return s;if (t.length() > s.length()) return "";int[] tCount = new int[128];for (char c : t.toCharArray()) tCount[c]++;int[] curCount = new int[128];int left = 0, right = 0;int min = Integer.MAX_VALUE;int matchedChars = 0;int start = 0;// 重点: 外层循环不断扩展右边界while (right < s.length()) {char rightChar = s.charAt(right);// 当前右边界的字符出现在字符串t中if (tCount[rightChar] > 0) {// 更新匹配好的字符数量if (curCount[rightChar] < tCount[rightChar]) matchedChars++;curCount[rightChar]++;}// 重点: 内层for循环缩减左边界// 如果匹配好的字符数量跟字符串t的长度相同了while (matchedChars == t.length()) {if (right - left < min) {min = right - left + 1;start = left;}char leftChar = s.charAt(left);if (tCount[leftChar] > 0) {// 如果减去当前left的字符会不满足字符串t, 那么更新matchedChars来跳出循环if (curCount[leftChar] == tCount[leftChar]) matchedChars--;curCount[leftChar]--;}left++;}right++;}if (min == Integer.MAX_VALUE) return "";return s.substring(start, start + min);
}