Sliding Window 演算法 簡介

快速解出SubArray的演算法

簡介

主要用來快速找出連續的SubString, SubArray，找出符合條件的最小or最大值。

實際範例

給定一個總和，並從陣列中找出「大於等於」該總和的SubArray的長度「最小值」

Input: sum = 7, nums = [2, 3, 1, 2, 4, 3]
Output: 2
Explanation: SubArray [4, 3]有最小的length
(4 + 3 >= 7)

• 暴力法

最簡單且直覺的就是「窮盡」所有SubArray，找出所有的可能並進行分別比對，直到找出最小值。

時間複雜度是 O(n³)

const solveBrutally = (arr=[], sum=0) => {
  let minLength = Infinity;
  if(SUM(arr) < sum) {
    return undefined;
  }
  for (let i = 0; i < arr.length; i++) {
    for (let innerIdx = i; innerIdx < arr.length; innerIdx++) {
      const subArr = arr.slice(i, innerIdx + 1);
      if(SUM(subArr) === sum) {
        if(subArr.length < minLength) {
          minLength = subArr.length;
        }
      }
    }
  }
  return minLength;
}
solveBrutally([2, 3, 1, 2, 4, 3], 7) // 2
// 產出所有的SubArray做比較
// [1], [1, 2], [1, 2, 3]...
// [2], [2, 3], [2, 3, 4]...

• 更好的解法 — Sliding Window

基於暴力法的改良，就是WindowSliding這個演算法。

方法是用「兩個指針」來交替移動找出「交集」，分別是 start （指針的頭）和 end （指針的尾）。就像是窗戶的左邊框框和右邊框框，將其搜尋範圍縮限在這個start和end的範圍之內，而這窗框的大小(size)通常就是問題需要的答案。

之所以能用start和end找出答案，是因為「沒必要」找出所有解答，像是[2, 3, 1, 2] 就已經大於等於7了，那就沒必要找[2, 3, 1, 2, 4]，因為長度(length)一定比較上一個還大（我們要找最小長度）。這樣我們可以將start移動到右邊(+= 1)找下一個SubArray的群集，用while迴圈繼續找下去，直到找出最小值。

簡單來說，就是先給定一個固定範圍（窗戶框）, 然後這個窗戶會開開關關，窗戶框會左右移動（移動窗戶的同時開關窗戶），只要確保範圍不超過我們問題所要求的值就好。

時間複雜度是 O(n)

const solveBySlidingWindow = (arr=[], sum=0) => {
  let sumNow = 0, startNow = 0;
  let minSize = Infinity;
  for (let endNow = 0; endNow < arr.length; endNow++) {
    sumNow += arr[endNow];
    while(sumNow >= sum) {
      const windowSize = endNow - startNow + 1;
      console.log(arr.slice(startNow, endNow + 1)); // 印出目前窗框範圍內的SubArray
      minSize = Math.min(minSize, windowSize); // 更新最小size
      // 窗框往右移動
      sumNow -= arr[startNow]; // 減去原本的start
      startNow++; // start往右移動
    }
  }
  return minSize === Infinity ? 0 : minSize;
};
solveBySlidingWindow([2, 3, 1, 2, 4, 3], 7) // 2
// 只產出符合窗框範圍的SubArray做比較(用startNow和endNow取得目前的SubArray)
// [2, 3, 1, 2] start: 0, end: 3
// [3, 1, 2, 4] start: 1, end: 4
// [1, 2, 4] start: 2, end: 4
// [2, 4, 3] start: 3, end: 5
// [4, 3] start: 4, end: 5, 長度最小值

其他問題與範例

還有兩個問題，記在CodePen的程式碼中了，可以把console註解掉看output結果。

CodePen Embed - Sliding Window Sample

主要參考來源

主要是將以下這篇文章中用c語言寫的範例，轉為JavaScript，並做些簡化與整理。

https://blog.techbridge.cc/2019/09/28/leetcode-pattern-sliding-window/#post-comment-wrapper