面試工具包：陣列 - 滑動視窗。

一切都與模式有關！

一旦你學會了這些模式，一切都開始變得更容易了！如果你像我一樣，你可能不喜歡技術面試，我不怪你——面試可能很艱難。

陣列問題是面試中最常見的問題。這些問題通常涉及使用自然數組：

const arr = [1, 2, 3, 4, 5];

還有字串問題，本質上是字元陣列：

"mylongstring".split(""); // ['m', 'y', 'l', 'o','n', 'g', 's','t','r','i', 'n', 'g']

解決陣列問題最常見的模式之一是滑動視窗。

滑動視窗模式

滑動視窗模式涉及兩個沿同一方向移動的指針，就像在數組上滑動的視窗一樣。

何時使用它

當您需要尋找符合特定條件（例如最小值、最大值、最長或）的子陣列或子字串時，請使用滑動視窗模式最短。

規則1：如果需要尋找子陣列或子字串，且資料結構是陣列或字串，請考慮使用滑動視窗模式。

簡單的例子

這是一個介紹滑動視窗中指標概念的基本範例：

function SlidingWindow(arr) {
    let l = 0;  // Left pointer
    let r = l + 1;  // Right pointer

    while (r < arr.length) {
        console.log("left", arr[l]);
        console.log("right", arr[r]);
        l++;
        r++;
    }
}

SlidingWindow([1, 2, 3, 4, 5, 6, 7, 8]);

請注意，左（L）和右（R）指針不必同時移動，但必須朝同一方向移動。

右指針永遠不會低於左指針。

讓我們透過一個真實的面試問題來探索這個概念。

現實問題：不重複字元最長的子字串

問題：給定一個字串 s，找出不包含重複字元的最長子字串的長度。

關鍵字： 子-字串，最長（最大）

function longestSubstr(str) {
    let longest = 0;
    let left = 0;
    let hash = {};

    for (let right = 0; right < str.length; right++) {
        if (hash[str[right]] !== undefined && hash[str[right]] >= left) {
            left = hash[str[right]] + 1;
        }

        hash[str[right]] = right;
        longest = Math.max(longest, right - left + 1);
    }

    return longest;
}

如果這看起來很複雜，請不要擔心——我們會一點一點地解釋它。

let str = "helloworld";
console.log(longestSubstr(str));  // Output: 5

這個問題的核心是找到最長的子字串沒有重複字元。

初始視窗：大小 0

開始時，左（L）和右（R）指針都位於同一位置：

let left = 0;

for (let right = 0; right < str.length; right++) {  // RIGHT POINTER

h e l l o w o r l d 
^
^
L
R

我們有一個空的雜湊（物件）：

let hash = {};

物體有什麼偉大之處？它們儲存唯一的鍵，這正是我們解決這個問題所需要的。我們將使用哈希來追蹤我們訪問過的所有字符，並檢查我們之前是否見過當前字符（以檢測重複項）。

透過查看字串，我們可以直觀地看出world是最長的沒有重複字元的子字串：

h e l l o w o r l d 
          ^        ^   
          L        R

它的長度是 5。那麼，我們要如何到達那裡？

讓我們一步一步分解：

初始狀態

hash = {}

h e l l o w o r l d 
^
^
L
R

迭代 1：

在每次迭代中，我們將 R 指標下的字元新增至雜湊映射中並遞增：

hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);

目前，我們的視窗中沒有重複字元（h 和 e）：

hash = {h: 0}
h e l l o w o r l d 
^ ^
L R

迭代 2：

hash = {h: 0, e: 1}
h e l l o w o r l d 
^   ^
L   R

現在，我們有一個新視窗：hel。

迭代 3：

hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
^     ^
L     R

這就是有趣的地方：我們的雜湊中已經有 l，而 R 指向字串中的另一個 l。這就是我們的 if 語句出現的地方：

if (hash[str[right]] !== undefined)

如果我們的雜湊包含 R 指向的字母，我們就發現了一個重複！上一個視窗 (hel) 是我們迄今為止最長的窗口。

那麼，接下來我們該做什麼？由於我們已經處理了左子字串，因此我們透過向上移動 L 指標來從左側縮小視窗。但我們要把 L 移動多遠？

left = hash[str[right]] + 1;

我們將 L 移到重複項之後：

hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
      ^
      ^
      L
      R

我們仍然將重複項新增到雜湊中，因此 L 現在的索引為 3。

hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);

新狀態：迭代 4

hash = {h: 0, e: 1, l: 3}
h e l l o w o r l d 
      ^ ^
      L R

迭代 4 至 6

hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
      ^     ^
      L     R

當 R 指向另一個重複項 (o) 時，我們將 L 移到第一個 o 之後：

hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
          ^ ^
          L R

我們繼續，直到遇到另一個重複的 l:

hash = {h: 0, e: 1, l: 3, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^     ^
          L     R

但請注意它在當前視窗之外！從 w 開始，

規則 3：忽略已處理的子 x

當前視窗之外的任何內容都是無關緊要的——我們已經處理了它。管理這個的關鍵程式碼是：

if (hash[str[right]] !== undefined && hash[str[right]] >= left)

此條件確保我們只關心當前視窗內的字符，過濾掉任何噪音。

hash[str[right]] >= left

我們專注於任何大於或等於左指標的東西

最終迭代：

hash = {h: 0, e: 1, l: 8, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^       ^
          L       R

我知道這很詳細，但是將問題分解為更小的模式或規則是掌握它們的最簡單方法。

In Summary:

• Rule 1: Keywords in the problem (e.g., maximum, minimum) are clues. This problem is about finding the longest sub-string without repeating characters.
• Rule 2: If you need to find unique or non-repeating elements, think hash maps.
• Rule 3: Focus on the current window—anything outside of it is irrelevant.

Bonus Tips:

• Break down the problem and make it verbose using a small subset.
• When maximizing the current window, think about how to make it as long as possible. Conversely, when minimizing, think about how to make it as small as possible.

To wrap things up, here's a little challenge for you to try out! I’ll post my solution in the comments—it’s a great way to practice.

Problem 2: Sum Greater Than or Equal to Target

Given an array, find the smallest subarray with a sum equal to or greater than the target(my solution will be the first comment).

/**
 * 
 * @param {Array<number>} arr 
 * @param {number} target 
 * @returns {number} - length of the smallest subarray
 */
function greaterThanOrEqualSum(arr, target){
   let minimum = Infinity;
   let left = 0;
   let sum = 0;

   // Your sliding window logic here!
}

Remember, like anything in programming, repetition is key! Sliding window problems pop up all the time, so don’t hesitate to Google more examples and keep practicing.

I’m keeping this one short, but stay tuned—the next article will dive into the two-pointer pattern and recursion (prepping for tree problems). It’s going to be a bit more challenging!

If you want more exclusive content, you can follow me on Twitter or Ko-fi I'll be posting some extra stuff there!

Resources:

Tech interview Handbook

leet code arrays 101

以上是面試工具包：陣列 - 滑動視窗。的詳細內容。更多資訊請關注PHP中文網其他相關文章！