面试工具包：数组 - 滑动窗口。

一切都与模式有关！

一旦你学会了这些模式，一切都开始变得更容易了！如果你像我一样，你可能不喜欢技术面试，我不怪你——面试可能很艰难。

数组问题是面试中最常见的问题。这些问题通常涉及使用自然数组：

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中文网其他相关文章！