一切都与模式有关！

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

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

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 



注意左(L)和右(R)指针不必同时移动，但必须朝同一方向移动。



右指针永远不会低于左指针。

让我们通过一个真实的面试问题来探讨这个概念。


  
  
  现实问题：不重复字符的最长子串


问题：给定一个字符串s，求不重复字符的最长子串的长度。

关键字： 子-字符串，最长（最大）


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

    for (let right = 0; 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 





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




我知道这很详细，但是将问题分解为更小的模式或规则是掌握它们的最简单方法。


  
  
  总之：

• 规则1：问题中的关键词（例如最大值、最小值）是线索。本题是求最长的子串不带重复字符。
• 规则 2： 如果您需要查找唯一或不重复的元素，请考虑哈希映射。
• 规则 3： 关注当前窗口——窗口之外的任何内容都是无关紧要的。

奖金提示：

• 使用一个小子集分解问题并使其变得冗长。
• 最大化当前窗口时，考虑如何使其尽可能长。反之，最小化的时候，想想如何让它尽可能的小。

最后，这里有一个小挑战供您尝试！我将在评论中发布我的解决方案 - 这是一种很好的练习方式。

问题 2：总和大于或等于目标

给定一个数组，找到总和等于或大于目标的最小子数组（我的解决方案将是第一个注释）。

/**
 * 
 * @param {Array} 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!
}

记住，就像编程中的任何事情一样，重复是关键！滑动窗口问题总是会出现，所以不要犹豫，谷歌更多的例子并继续练习。

我的这篇文章很简短，但请继续关注——下一篇文章将深入探讨两指针模式和递归（为树问题做准备）。这将会更具挑战性！

如果您想要更多独家内容，您可以在 Twitter 或 Ko-fi 上关注我，我会在那里发布一些额外的内容！

资源：

技术面试手册

leet代码数组101