#209 Minimum Size Subarray Sum

Sliding Window

LeetCode

Given an array of n positive integers and a positive
integer s, find the minimal length of a contiguous subarray
of which the sum ≥ s. If there isn't one, return 0 instead.

Example: 

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length 
under the problem constraint.

/**
 * @param {number} s
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(s, nums) {}

擷取自 Leetcode 刷題 pattern - Sliding Window

Sliding Window 解法

如果我們仔細觀察暴力法的過程，就會發現有很多 subarray sum 是重複計算的！我們看看下面這個例子

nums = [2,3,1,2,4,3]
暴力法列舉出的 subarrays =
[2]
[2,3]
[2,3,1]
[2,3,1,2]
[2,3,1,2,4]
[2,3,1,2,4,3]
 
[3]
[3,1]
[3,1,2]
[3,1,2,4]
[3,1,2,4,3]
 
...
...

不難發現，其實以 2 為開頭的 subarray 跟以 3 為開頭的 subarray 其實只差在開頭有沒有那個 2，後面的數值應該要可以重複利用！

所以我們可以用 windowStart 跟 windowEnd 兩個指向 subarray 邊界的指針，來控制我們現在要看的 subarray。演算法就是要先一直擴張 windowEnd，如果發現 windowSum 已經比 s 大，那就開始縮減 window（也就是把 windowStart 往右移），直到走到 nums 的尾巴。實做出來的程式碼如下

var minSubArrayLen = function(s, nums) {
    let min = Number.MAX_SAFE_INTEGER;
    let sum = 0, start = 0;
    for(let end = 0; end < nums.length; end++){
        sum += nums[end];
        while(sum >= s){
            min = Math.min(min, end -  start + 1);
            
            // 也就是把 windowStart 往右移
            sum -= nums[start];
            start ++;
        }
        
  }
   
  return min == Number.MAX_SAFE_INTEGER ? 0 : min;
};

使用這個方法，就完全去除掉冗餘的計算，讓時間複雜度下降到 O(n)O(n)！剛開始學到這個演算法的時候會懷疑這樣真的能走過所有可能的 subarray 嗎？

我覺得大家可以透過這個例子觀察

nums = [2,3,1,2,4,3], s = 7
暴力法列舉出的 subarrays =
[2]
[2,3]
[2,3,1]
[2,3,1,2] // WindowStart 會開始往右移
[2,3,1,2,4]
[2,3,1,2,4,3]
 
...

一開始 windowStart 指向 2，然後 windowEnd 會慢慢擴張，當擴張到 [2,3,1,2] 這個情況時，因為 sum 已經 >= 7，所以 windowStart 會開始右移。也就是說，原本暴力法會考慮的 [2,3,1,2,4] 跟 [2,3,1,2,4,3] 就不會被考慮到。

就是因為這種情況，直觀下會覺得我們這樣不就少考慮到很多情況嗎？

但大家可以再仔細想想，我們現在要求的是 sum >= s 的最小 subarray，如果 [2,3,1,2] 已經滿足條件了，我們繼續看 [2,3,1,2,4] 跟 [2,3,1,2,4,3] 又有什麼意義呢？畢竟這兩個 subarray 都大於 [2,3,1,2] 啊！

只要把這點想通了，就不會再有用 Sliding Window 沒有考慮到所有 case 的這種讓心裡隱約覺得不對的想法！接著讓我們繼續看下去，更加熟悉 Sliding Window 可以應用的場景。