本篇博客講解LeetCode熱題100道子串篇中的三道題

第一道：和為 K 的子數(shù)組

第二道：滑動(dòng)窗口最大值

第三道：最小覆蓋子串

第一道：和為 K 的子數(shù)組（中等）

法一：暴力枚舉

 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;}
}

思想比較簡(jiǎn)單，找到所有子數(shù)組的和，如果等于目標(biāo)值target。那么count++

最終返回count

法二：前綴和 + 哈希表優(yōu)化

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;}
}

前綴和：是求解子數(shù)組的和等問(wèn)題的好方法。通過(guò)累加數(shù)組中的值，使其減去數(shù)組中某個(gè)值來(lái)得到子數(shù)組的和。?

前綴和用法示例:?

?

建哈希表優(yōu)化后。?

?

前綴和： 使用pre += nums[i]; 用pre變量來(lái)累加前綴和。只需要pre即可。

因?yàn)槲覀冎恍枰美奂雍蜏p去目標(biāo)值target。再去哈希表中找有沒(méi)有對(duì)應(yīng)的值。

如果有對(duì)應(yīng)的值，說(shuō)明存在子數(shù)組的和為target。那么count++

最終返回conunt

第二道：滑動(dòng)窗口最大值（困難）

法一：優(yōu)先隊(duì)列

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. 定義一個(gè)優(yōu)先隊(duì)列（最大堆）pQueue，用于存儲(chǔ)滑動(dòng)窗口內(nèi)的元素。隊(duì)列按照元素值降序排列，如果值相同則按索引降序排列。
2. 初始化隊(duì)列，將數(shù)組前 k 個(gè)元素加入隊(duì)列。
3. 創(chuàng)建結(jié)果數(shù)組 ans，用于存儲(chǔ)每個(gè)窗口的最大值。
4. 將隊(duì)列頂部（最大值）的元素值存入結(jié)果數(shù)組的第一個(gè)位置。
5. 從第 k 個(gè)元素開(kāi)始，逐步將元素加入隊(duì)列，并移除不在當(dāng)前滑動(dòng)窗口內(nèi)的元素（根據(jù)索引判斷）。
6. 每次移動(dòng)窗口后，將當(dāng)前窗口的最大值（隊(duì)列頂部元素值）存入結(jié)果數(shù)組相應(yīng)位置。
7. 最終返回結(jié)果數(shù)組。

?使用優(yōu)先隊(duì)列高效地計(jì)算了數(shù)組中每個(gè)滑動(dòng)窗口的最大值。

?法二：單調(diào)隊(duì)列（單調(diào)性的雙端隊(duì)列）

單調(diào)隊(duì)列套路

• 入（元素進(jìn)入隊(duì)尾，同時(shí)維護(hù)隊(duì)列單調(diào)性）
• 出（元素離開(kāi)隊(duì)首）
• 記錄/維護(hù)答案（根據(jù)隊(duì)首）

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. 初始化一個(gè)雙端隊(duì)列，用于存儲(chǔ)數(shù)組元素的索引。
2. 遍歷數(shù)組前 k 個(gè)元素，保持隊(duì)列中元素對(duì)應(yīng)的數(shù)組值按降序排列，并存儲(chǔ)這些元素的索引。
3. 初始化結(jié)果數(shù)組 ans 并將第一個(gè)窗口的最大值（隊(duì)列頭部的元素）存入 ans 的第一個(gè)位置。
4. 遍歷數(shù)組剩余元素：

• 將新的元素索引加入隊(duì)列，并移除隊(duì)列中所有比當(dāng)前元素小的元素的索引。
• 移除隊(duì)列中不在當(dāng)前窗口范圍內(nèi)的索引。
• 將當(dāng)前窗口的最大值（隊(duì)列頭部的元素）存入 ans 的相應(yīng)位置。

最終返回結(jié)果數(shù)組 ans。

法三：分塊 + 預(yù)處理

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;}
}

?

• 初始化前綴最大值和后綴最大值數(shù)組：

  • prefixMax[i] 表示從塊的開(kāi)始到索引 i 的最大值。
  • suffixMax[i] 表示從索引 i 到塊的結(jié)束的最大值。

• 構(gòu)建前綴最大值數(shù)組：

  • 遍歷數(shù)組，如果索引 i 是塊的開(kāi)始，prefixMax[i] 等于 nums[i]。
  • 否則，prefixMax[i] 等于 prefixMax[i - 1] 和 nums[i] 的最大值。

• 構(gòu)建后綴最大值數(shù)組：

  • 從數(shù)組末尾遍歷，如果索引 i 是塊的結(jié)束，suffixMax[i] 等于 nums[i]。
  • 否則，suffixMax[i] 等于 suffixMax[i + 1] 和 nums[i] 的最大值。

• 計(jì)算每個(gè)滑動(dòng)窗口的最大值：

  • 遍歷 ans 數(shù)組，每個(gè)窗口的最大值是 suffixMax[i] 和 prefixMax[i + k - 1] 的最大值。

• 返回結(jié)果數(shù)組：

  • 返回存有每個(gè)滑動(dòng)窗口最大值的結(jié)果數(shù)組 ans

第三道：最小覆蓋子串（困難）

?

方法一：滑動(dòng)窗口?

?

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 中每個(gè)字符出現(xiàn)的次數(shù)。
  • 使用 cnt 哈希表記錄當(dāng)前窗口中每個(gè)字符的出現(xiàn)次數(shù)。

• 滑動(dòng)窗口的初始化：

  • 初始化左指針 l 和右指針 r，分別表示當(dāng)前窗口的左右邊界。
  • 初始化記錄最小窗口長(zhǎng)度的 len 和最小窗口的起始和結(jié)束位置 ansL 和 ansR。

• 滑動(dòng)窗口擴(kuò)展：

  • 移動(dòng)右指針擴(kuò)展窗口，若當(dāng)前字符在 t 中，將其加入 cnt。

• 縮小窗口：

  • 當(dāng)窗口內(nèi)包含了 t 中所有字符時(shí)，嘗試縮小窗口：
    • 如果當(dāng)前窗口長(zhǎng)度小于已記錄的最小窗口長(zhǎng)度，更新最小窗口的位置和長(zhǎng)度。
    • 移動(dòng)左指針，若左指針指向的字符在 t 中，將其從 cnt 中移除。

• 返回結(jié)果：

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

• 輔助方法 check：

  • 檢查當(dāng)前窗口是否包含 t 中所有字符，即 cnt 中每個(gè)字符的數(shù)量是否都不小于 ori 中對(duì)應(yīng)的數(shù)量。