hot100-子串-JS

一、560.和為k的子串

560. 和為 K 的子數組
?
提示

給你一個整數數組 nums 和一個整數?k ，請你統計并返回 該數組中和為?k?的子數組的個數?。

子數組是數組中元素的連續非空序列。

示例 1：
輸入：nums = [1,1,1], k = 2
輸出：2
示例 2：
輸入：nums = [1,2,3], k = 3
輸出：2
提示：

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

1.暴力枚舉法

暴力枚舉的基本思路是通過兩層循環來枚舉所有可能的子數組，然后計算每個子數組的和，判斷其是否等于目標值?k，如果相等則將計數器加 1。

/*** @param {number[]} nums* @param {number} k* @return {number}*/
var subarraySum = function (nums, k) {let count = 0;for (let i = 0; i < nums.length; i++) {let sum = 0;for (let j = i; j < nums.length; j++) {sum += nums[j];if (sum === k) {count++}}}return count;
};

2.使用前綴和與哈希表（推薦）

問題分析

給定一個整數數組?nums?和一個整數?k，要找出數組中和為?k?的子數組（連續非空元素序列）的個數。例如，對于數組?[1, 1, 1]?和?k = 2，子數組?[1, 1]?滿足和為?2，所以結果是?2。

前綴和的引入

前綴和是指從數組開頭到當前位置的所有元素的和。假設我們有一個數組?nums = [a0, a1, a2, ..., an]，那么：

前綴和?prefixSum[0] = a0；
前綴和?prefixSum[1] = a0 + a1；
前綴和?prefixSum[2] = a0 + a1 + a2；
以此類推，prefixSum[i] = a0 + a1 + ... + ai。

對于計算子數組和，有一個重要的性質：如果我們要找從索引?j?到索引?i（j <= i）的子數組和，那么這個子數組和?subarraySum(j, i)?就等于?prefixSum[i] - prefixSum[j - 1]（當?j > 0?時），如果?j = 0，則?subarraySum(j, i) = prefixSum[i]。

算法思路推導

我們的目標是找到滿足?subarraySum(j, i) = k?的子數組個數。根據上面的前綴和性質，subarraySum(j, i) = prefixSum[i] - prefixSum[j - 1] = k，可以變形為?prefixSum[j - 1] = prefixSum[i] - k。

這意味著，如果我們知道所有前綴和的值以及它們出現的次數，那么對于當前計算得到的前綴和?prefixSum[i]，我們只需要檢查之前是否出現過?prefixSum[i] - k?這個前綴和。如果出現過，那么就說明存在一個子數組的和為?k，并且出現次數就是?prefixSum[i] - k?出現的次數。

哈希表的作用

為了高效地存儲和查詢前綴和及其出現的次數，我們使用哈希表（在 JavaScript 中是?Map?對象）。具體步驟如下：

?初始化?：
- 創建一個空的?Map?對象?map，用于存儲前綴和及其出現的次數。
- 初始化?map.set(0, 1)，這是因為前綴和為?0?的情況是存在的（對應空數組，空數組的和為?0），出現次數為?1。
- 初始化變量?sum = 0?來記錄當前的前綴和，ans = 0?來記錄和為?k?的子數組的個數。
?遍歷數組?：
- 對于數組中的每個元素?num，將其加到當前前綴和?sum?中，即?sum += num。
- 檢查?map?中是否存在?sum - k。如果存在，說明存在一個子數組的和為?k，將?map.get(sum - k)的值加到?ans?中。這是因為?sum - (sum - k) = k，map.get(sum - k)?表示之前出現過?sum - k?這個前綴和的次數，也就意味著有這么多組子數組的和為?k。
- 將當前前綴和?sum?及其出現的次數存入?map?中。如果?sum?已經存在于?map?中，將其出現次數加?1；否則，將其出現次數設為?1。
?返回結果?：
- 遍歷結束后，ans?中存儲的就是和為?k?的子數組的個數，將其返回。

示例分析

以輸入?nums = [1, 1, 1]，k = 2?為例：

初始化：map = {0: 1}，sum = 0，ans = 0。
第一次循環：
- num = 1，sum = 0 + 1 = 1。
- 檢查?map?中是否有?1 - 2 = -1，沒有。
- map.set(1, 1)（現在?map = {0: 1, 1: 1}）。
- ans?不變，仍為?0。
第二次循環：
- num = 1，sum = 1 + 1 = 2。
- 檢查?map?中是否有?2 - 2 = 0，有，ans = ans + map.get(0) = 0 + 1 = 1。
- map.set(2, 1)（現在?map = {0: 1, 1: 1, 2: 1}）。
第三次循環：
- num = 1，sum = 2 + 1 = 3。
- 檢查?map?中是否有?3 - 2 = 1，有，ans = ans + map.get(1) = 1 + 1 = 2。
- map.set(3, 1)（現在?map = {0: 1, 1: 1, 2: 1, 3: 1}）。
最終返回?ans = 2，符合預期。

通過這樣的方式，使用前綴和與哈希表的方法能夠高效地解決“和為 K 的子數組”問題。希望以上解釋能幫助你理解這個算法的原理和實現過程。

代碼實現

/*** @param {number[]} nums* @param {number} k* @return {number}*/
var subarraySum = function (nums, k) {let map=new Map();// 初始設置為0的元素有1個map.set(0,1);let sum=0;let ans=0;for(let num of nums){// 計算元素的前綴和sum+=num;// 計數，統計前綴和為某個數共有多少個map.set(sum,(map.has(sum)||0)+1)// 判斷map中是否有 sum-k 如果存在，說明存在一個子數組的和為 kif(map.has(sum-k)){// 將 map.get(sum - k)的值加到 ans 中ans+=map.get(sum-k);}}return ans;
};

二、239.滑動窗口最大值

239. 滑動窗口最大值
?
給你一個整數數組 nums，有一個大小為?k?的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口內的 k?個數字。滑動窗口每次只向右移動一位。

返回 滑動窗口中的最大值 。

示例 1：
輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3
輸出：[3,3,5,5,6,7]
解釋：
滑動窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7
示例 2：
輸入：nums = [1], k = 1
輸出：[1]
提示：

1 <= nums.length <= 105
-104?<= nums[i] <= 104
1 <= k <= nums.length

1.暴力法（超出時間限制）

O(nk)會很慢

/*** @param {number[]} nums* @param {number} k* @return {number[]}*/
function maxSlidingWindow(nums, k) {let result=[]for (let i = 0; i < nums.length - k + 1; i++) {let max = -Infinity;for (let j = i; j < i + k; j++) {max = Math.max(nums[j], max)}result.push(max)}return result
}

2.優化解法（雙端隊列，時間復雜度 O(n)）??

算法思路

?初始化數據結構?：
- q?數組模擬單調棧，它的作用是存儲數組?nums?中元素的下標，并且保證棧內元素對應的?nums?值從棧底到棧頂是單調遞減的。這樣，棧頂元素對應的?nums?值始終是當前窗口內的最大值（或者候選最大值）。
- ans?數組用于存儲每個滑動窗口的最大值，最終作為函數的返回結果。
?遍歷數組過程?：
- ?維護單調性?：在每次將新元素?nums[i]?考慮加入窗口時，通過?while?循環檢查棧頂元素。如果當前元素?nums[i]?大于等于棧頂元素對應的?nums?值，就不斷彈出棧頂元素。這是因為棧頂元素不可能是當前窗口內的最大值了，通過這樣的操作保證了棧的單調性。
- ?加入新元素?：將當前元素的下標?i?壓入棧?q?中，以便后續判斷該元素是否在窗口內以及作為可能的最大值候選。
- ?檢查窗口范圍?：檢查棧頂元素的下標是否已經不在當前窗口范圍內（即小于等于?i - k）。如果是，說明該元素已經隨著窗口的滑動移出了當前窗口，需要將其從棧頂彈出，以確保棧中元素對應的下標都在當前窗口內。
- ?記錄最大值?：當窗口已經形成（即?i >= k - 1，因為前?k - 1?個元素構不成完整窗口）時，棧頂元素對應的?nums?值就是當前窗口的最大值，將其加入到?ans?數組中。
?返回結果?：遍歷完整個數組?nums?后，ans?數組中已經存儲了每個滑動窗口的最大值，將其返回。

示例演示

給定的示例?nums = [1, 3, -1, -3, 5, 3, 6, 7]，k = 3?為例，詳細演示如何計算滑動窗口最大值的：

初始化

初始化?q?為一個空數組，用于模擬單調棧，存儲數組元素的下標；初始化?ans?為一個空數組，用于存儲每個滑動窗口的最大值。
i?初始化為?0，開始遍歷數組?nums。

第一次循環 (i = 0)

nums[0] = 1，此時?q?為空，將?i = 0?壓入?q，即?q = [0]。
因為?q?只有一個元素，它的下標?0?滿足?0 >= 0 - 3（此時窗口還未完全形成，這里條件看似不成立但后續會處理），不執行?q.shift()。
由于?i = 0 < 3 - 1，窗口還未形成，不執行?ans.push(nums[q[0]])。

第二次循環 (i = 1)

nums[1] = 3，因為?3 >= nums[q[q.length - 1]]（即?3 >= nums[0]，nums[0] = 1），執行?q.pop()，此時?q = [1]。
將?i = 1?壓入?q，q = [1]。
因為?q[0] = 1，1 < 1 - 3?不成立，不執行?q.shift()。
由于?i = 1 < 3 - 1，窗口還未形成，不執行?ans.push(nums[q[0]])。

第三次循環 (i = 2)

nums[2] = -1，因為?-1 < nums[q[q.length - 1]]（即?-1 < nums[1]，nums[1] = 3），不執行?q.pop()。
將?i = 2?壓入?q，q = [1, 2]。
因為?q[0] = 1，1 < 2 - 3?不成立，不執行?q.shift()。
由于?i = 2 >= 3 - 1，窗口已經形成，執行?ans.push(nums[q[0]])，即?ans = [3]。

第四次循環 (i = 3)

nums[3] = -3，因為?-3 < nums[q[q.length - 1]]（即?-3 < nums[2]，nums[2] = 3），不執行?q.pop()。
將?i = 3?壓入?q，q = [1, 2, 3]。
因為?q[0] = 1，1 < 3 - 3?不成立，不執行?q.shift()。
由于?i = 3 >= 3 - 1，窗口已經形成，執行?ans.push(nums[q[0]])，即?ans = [3, 3]。

第五次循環 (i = 4)

nums[4] = 5，因為?5 >= nums[q[q.length - 1]]（即?5 >= nums[3]，nums[3] = -3），執行?q.pop()，此時?q = [1, 2]。
因為?5 >= nums[q[q.length - 1]]（即?5 >= nums[2]，nums[2] = 3），再執行?q.pop()，此時?q = [1]。
將?i = 4?壓入?q，q = [1]。
因為?q[0] = 1，1 < 4 - 3?不成立，不執行?q.shift()。
由于?i = 4 >= 3 - 1，窗口已經形成，執行?ans.push(nums[q[0]])，即?ans = [3, 3, 5]。

第六次循環 (i = 5)

nums[5] = 3，因為?3 >= nums[q[q.length - 1]]（即?3 >= nums[1]，nums[1] = 1），執行?q.pop()，此時?q = [5]。
將?i = 5?壓入?q，q = [5]。
因為?q[0] = 5，5 < 5 - 3?不成立，不執行?q.shift()。
由于?i = 5 >= 3 - 1，窗口已經形成，執行?ans.push(nums[q[0]])，即?ans = [3, 3, 5, 5]。

第七次循環 (i = 6)

nums[6] = 6，因為?6 >= nums[q[q.length - 1]]（即?6 >= nums[5]，nums[5] = 3），執行?q.pop()，此時?q = [6]。
將?i = 6?壓入?q，q = [6]。
因為?q[0] = 6，6 < 6 - 3?不成立，不執行?q.shift()。
由于?i = 6 >= 3 - 1，窗口已經形成，執行?ans.push(nums[q[0]])，即?ans = [3, 3, 5, 5, 6]。

第八次循環 (i = 7)

nums[7] = 7，因為?7 >= nums[q[q.length - 1]]（即?7 >= nums[6]，nums[6] = 6），執行?q.pop()，此時?q = [7]。
將?i = 7?壓入?q，q = [7]。
因為?q[0] = 7，7 < 7 - 3?不成立，不執行?q.shift()。
由于?i = 7 >= 3 - 1，窗口已經形成，執行?ans.push(nums[q[0]])，即?ans = [3, 3, 5, 5, 6, 7]。

循環結束

遍歷完整個數組?nums?后，ans?數組中存儲了每個滑動窗口的最大值，最終返回?ans = [3, 3, 5, 5, 6, 7]。

代碼實現

var maxSlidingWindow = function(nums, k) {let q = []; // 用于模擬單調棧，存儲數組元素的下標let ans = []; // 用于存儲每個滑動窗口的最大值for (let i = 0; i < nums.length; i++) {// 當棧不為空，并且當前元素大于等于棧頂元素對應的nums值時while (q.length > 0 && nums[i] >= nums[q[q.length - 1]]) {q.pop(); // 彈出棧頂元素，因為它不可能是當前窗口內的最大值了}q.push(i); // 將當前元素的下標壓入棧中// 如果棧頂元素的下標已經不在當前窗口范圍內（即小于等于i - k）if (q[0] <= i - k) {q.shift(); // 彈出棧頂元素，因為它已經不在當前窗口內了}// 當窗口已經形成（即i >= k - 1，因為前k - 1個元素構不成完整窗口）if (i >= k - 1) {ans.push(nums[q[0]]); // 將棧頂元素對應的nums值（也就是當前窗口的最大值）加入到結果數組ans中}}return ans;
};