1. 和為 k 的子數(shù)組

題目描述

給定一個整數(shù)數(shù)組 nums 和一個整數(shù) k，你需要在數(shù)組中找到連續(xù)子數(shù)組的個數(shù)，使得這些子數(shù)組的和等于 k。

解題思路

我們可以通過 前綴和 的方法來高效解決這個問題，結(jié)合 哈希表 來記錄每個前綴和出現(xiàn)的次數(shù)，從而迅速計算出滿足條件的子數(shù)組。

主要思路

1. 前綴和的定義：

   • 對于數(shù)組 nums，prefix[i] 表示從 nums[0] 到 nums[i-1] 的和。也就是說，prefix[i] = nums[0] + nums[1] + ... + nums[i-1]。
   • 子數(shù)組的和 nums[i..j] 可以表示為：prefix[j+1] - prefix[i]。因此，如果我們希望找到 nums[i..j] 的和為 k，那么只需要滿足 prefix[j+1] - prefix[i] = k。

2. 如何利用哈希表：

   • 在遍歷數(shù)組時，我們可以計算當(dāng)前的前綴和 pre。
   • 然后，我們通過 map.containsKey(pre - k) 來判斷是否存在一個前綴和為 pre - k 的位置，這樣就找到了一個子數(shù)組和為 k。
   • 我們還需要維護(hù)一個哈希表 map，其中 map.get(pre) 表示當(dāng)前前綴和 pre 出現(xiàn)的次數(shù)。這樣做是為了確保我們能夠計算出所有符合條件的子數(shù)組。

3. 核心算法：

   • 初始化哈希表 map，將 0 的計數(shù)初始化為 1，因為如果前綴和剛好為 k，就意味著從數(shù)組起始位置開始的子數(shù)組和為 k。
   • 遍歷數(shù)組并更新前綴和，并利用哈希表記錄前綴和的出現(xiàn)次數(shù)。

步驟

1. 初始化：

   • pre = 0 表示當(dāng)前的前綴和。
   • cnt = 0 表示符合條件的子數(shù)組數(shù)量。
   • map 存儲前綴和及其出現(xiàn)次數(shù)，初始時將 map.put(0, 1)，即前綴和為 0 出現(xiàn) 1 次。

2. 遍歷數(shù)組：

   • 對于每個元素，更新前綴和 pre。
   • 檢查哈希表中是否存在 pre - k，如果存在，說明從某個位置到當(dāng)前位置的子數(shù)組和為 k，則將其出現(xiàn)次數(shù)加到 cnt 中。
   • 更新哈希表，將當(dāng)前前綴和 pre 出現(xiàn)的次數(shù)加 1。

3. 返回結(jié)果：

   • 遍歷完所有元素后，cnt 中存儲的就是符合條件的子數(shù)組數(shù)量。

時間復(fù)雜度與空間復(fù)雜度

• 時間復(fù)雜度：O(n)，其中 n 是數(shù)組 nums 的長度。我們只需要遍歷一次數(shù)組，同時進(jìn)行常數(shù)時間的哈希表操作。
• 空間復(fù)雜度：O(n)，我們需要使用哈希表存儲前綴和及其出現(xiàn)次數(shù)，最壞情況下哈希表的大小為 n。

代碼實現(xiàn)

class Solution {public int subarraySum(int[] nums, int k) {int len = nums.length;int pre = 0, cnt = 0;HashMap<Integer, Integer> map = new HashMap<>();map.put(0, 1); // 初始化，前綴和為0的有1個，這樣做不會忽略掉“從數(shù)組起始位置開始的和為 k 的子數(shù)組”。for (int i = 0; i < len; i++) {pre += nums[i]; // 計算當(dāng)前前綴和if (map.containsKey(pre - k)) {  // 說明從某個位置到當(dāng)前位置存在連續(xù)子數(shù)組和為 kcnt = cnt + map.get(pre - k); // 增加符合條件的子數(shù)組的數(shù)量}// 更新哈希表，記錄當(dāng)前前綴和出現(xiàn)的次數(shù)map.put(pre, map.getOrDefault(pre, 0) + 1); }return cnt; // 返回符合條件的子數(shù)組數(shù)量}
}

2. 滑動窗口最大值

題目描述

給定一個整數(shù)數(shù)組 nums 和一個滑動窗口的大小 k，請你在數(shù)組中找出每個滑動窗口的最大值，并返回一個數(shù)組。

解題思路

這道題目是一個典型的滑動窗口問題。直接暴力計算每個窗口中的最大值的時間復(fù)雜度是 O(n*k)，這種做法在數(shù)據(jù)量較大的情況下效率較低。因此，我們可以使用 雙端隊列（Deque） 來優(yōu)化這一過程。

雙端隊列的原理：

• 雙端隊列是一種支持從兩端高效插入和刪除的隊列結(jié)構(gòu)。我們可以利用它來存儲數(shù)組元素的下標(biāo)，并保持隊列中的元素按照值的大小順序排列。這樣可以確保隊列的第一個元素永遠(yuǎn)是當(dāng)前窗口中的最大值。

優(yōu)化步驟：

及時去掉無用數(shù)據(jù)，保證雙端隊列有序（當(dāng)前數(shù)組>=隊尾，彈出隊尾；彈出隊首不在窗口內(nèi)的元素）

1. 使用一個雙端隊列 q 來存儲窗口中的元素的下標(biāo)。
2. 保證隊列中的元素下標(biāo)對應(yīng)的值是遞減的，隊列的首部始終是窗口的最大值。
3. 每次移動窗口時：
   • 入隊操作：將新元素的下標(biāo)加入隊列，并從隊列的尾部移除所有小于當(dāng)前元素的值，以保證隊列保持遞減順序。
   • 出隊操作：如果隊列頭部的元素已經(jīng)不再在當(dāng)前窗口范圍內(nèi)（即超出窗口的左邊界），則將其從隊列中移除。
   • 記錄結(jié)果：當(dāng)窗口大小達(dá)到 k 時，記錄當(dāng)前窗口的最大值，即隊列頭部的元素。

Java實現(xiàn)

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;Deque<Integer> q = new ArrayDeque<>(); // 存的是nums的下標(biāo)int[] ans = new int[n - k + 1];for (int i = 0; i < n; i++) {// 1. 入隊：保持隊列中的元素遞減while (!q.isEmpty() && nums[i] >= nums[q.getLast()]) {q.removeLast();}q.addLast(i); // 隊列存的是下標(biāo)// 2. 出隊：如果隊列的第一個元素不在窗口內(nèi)，移除它if (i - q.getFirst() >= k) {q.removeFirst();}// 3. 存結(jié)果：當(dāng)窗口大小達(dá)到k時，記錄最大值if (i >= k - 1) {ans[i - k + 1] = nums[q.getFirst()];}}return ans;}
}

3. 最小覆蓋子串

題目描述

給定字符串 s 和字符串 t，找到 s 中包含 t 中所有字符的最小子串。如果 s 中沒有包含 t 中所有字符的子串，則返回空字符串。

解題思路

這是一個經(jīng)典的滑動窗口問題。我們需要在字符串 s 中找到一個最小的子串，該子串包含了 t 中所有字符。最初我們可以考慮暴力解法，但暴力解法會超時，因此我們需要使用 滑動窗口 技巧來優(yōu)化算法。

滑動窗口的基本思路：

1. 滑動窗口的定義：我們維護(hù)一個窗口，窗口的大小是可變的，在窗口內(nèi)包含了 t 中的所有字符。
2. 擴(kuò)展窗口：從字符串 s 的開始位置開始擴(kuò)展窗口，逐步包含 t 中的字符。
3. 收縮窗口：當(dāng)窗口已經(jīng)包含了 t 中的所有字符時，嘗試縮小窗口的大小，以找到更小的符合條件的子串。
4. 窗口合法性：當(dāng)窗口內(nèi)包含所有 t 中的字符時，窗口是合法的。

具體步驟：

1. 使用兩個指針 left 和 right 表示滑動窗口的左右邊界，初始化時都指向字符串 s 的開頭。
2. 使用兩個哈希表 cntT 和 cntS 來記錄 t 中字符的出現(xiàn)頻率和當(dāng)前窗口中字符的出現(xiàn)頻率。
3. 當(dāng)窗口包含 t 中的所有字符時，嘗試縮小窗口的左邊界。
4. 在每次擴(kuò)展和收縮窗口時，更新當(dāng)前的最小子串。

算法的關(guān)鍵點：

• 記錄 t 中所有字符的頻率。
• 使用兩個指針維護(hù)滑動窗口。
• 記錄窗口內(nèi)字符的頻率并與 t 中的字符頻率進(jìn)行比較。

Java實現(xiàn)

class Solution {public String minWindow(String s, String t) {int ansLeft = -1;int m = s.length();int ansRight = m;// 記錄t的字符出現(xiàn)的次數(shù)Map<Character, Integer> cntT = new HashMap<>();for (char c : t.toCharArray()) {cntT.put(c, cntT.getOrDefault(c, 0) + 1);}// 記錄s的字符出現(xiàn)的次數(shù)Map<Character, Integer> cntS = new HashMap<>();int left = 0;int formed = 0;  // 記錄s和t覆蓋的字符的個數(shù)int required = cntT.size();  // 記錄t中的不同字符的個數(shù)for (int right = 0; right < m; right++) {char sr = s.charAt(right);cntS.put(sr, cntS.getOrDefault(sr, 0) + 1);// 如果s中的字符完全匹配t中的字符if (cntT.containsKey(sr) && cntS.get(sr).intValue() == cntT.get(sr).intValue()) {formed++;}// 當(dāng)s子串能覆蓋t的時候收縮窗口while (formed == required) {if (right - left < ansRight - ansLeft) {ansLeft = left;ansRight = right;}// 收縮窗口char leftChar = s.charAt(left);cntS.put(leftChar, cntS.get(leftChar) - 1);if (cntT.containsKey(leftChar) && cntS.get(leftChar).intValue() < cntT.get(leftChar).intValue()) {formed--;}left++;}}return ansLeft < 0 ? "" : s.substring(ansLeft, ansRight + 1); // 左閉右開}
}