搜尋
首頁web前端js教程面試工具包:陣列 - 滑動視窗。

一切都與模式有關!

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

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

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 



<p>請注意,左(L)和右(R)指針不必同時移動,但必須朝同一方向移動。 </p>

<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/172552892845227.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Interview Kit: Arrays - Sliding window."></p>

<p>右指針永遠不會低於左指針。 </p>

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

<h3>
  
  
  現實問題:不重複字元最長的子字串
</h3>

<p><strong>問題:</strong>給定一個字串 s,找出不包含重複字元的最長子字串的長度。 </p>

<p><strong>關鍵字:</strong> <em>子</em>-字串,最長(最大)<br>
</p>

<pre class="brush:php;toolbar:false">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 





<pre class="brush:php;toolbar:false">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!
}

</number>

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中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
JavaScript的角色:使網絡交互和動態JavaScript的角色:使網絡交互和動態Apr 24, 2025 am 12:12 AM

JavaScript是現代網站的核心,因為它增強了網頁的交互性和動態性。 1)它允許在不刷新頁面的情況下改變內容,2)通過DOMAPI操作網頁,3)支持複雜的交互效果如動畫和拖放,4)優化性能和最佳實踐提高用戶體驗。

C和JavaScript:連接解釋C和JavaScript:連接解釋Apr 23, 2025 am 12:07 AM

C 和JavaScript通過WebAssembly實現互操作性。 1)C 代碼編譯成WebAssembly模塊,引入到JavaScript環境中,增強計算能力。 2)在遊戲開發中,C 處理物理引擎和圖形渲染,JavaScript負責遊戲邏輯和用戶界面。

從網站到應用程序:JavaScript的不同應用從網站到應用程序:JavaScript的不同應用Apr 22, 2025 am 12:02 AM

JavaScript在網站、移動應用、桌面應用和服務器端編程中均有廣泛應用。 1)在網站開發中,JavaScript與HTML、CSS一起操作DOM,實現動態效果,並支持如jQuery、React等框架。 2)通過ReactNative和Ionic,JavaScript用於開發跨平台移動應用。 3)Electron框架使JavaScript能構建桌面應用。 4)Node.js讓JavaScript在服務器端運行,支持高並發請求。

Python vs. JavaScript:比較用例和應用程序Python vs. JavaScript:比較用例和應用程序Apr 21, 2025 am 12:01 AM

Python更適合數據科學和自動化,JavaScript更適合前端和全棧開發。 1.Python在數據科學和機器學習中表現出色,使用NumPy、Pandas等庫進行數據處理和建模。 2.Python在自動化和腳本編寫方面簡潔高效。 3.JavaScript在前端開發中不可或缺,用於構建動態網頁和單頁面應用。 4.JavaScript通過Node.js在後端開發中發揮作用,支持全棧開發。

C/C在JavaScript口譯員和編譯器中的作用C/C在JavaScript口譯員和編譯器中的作用Apr 20, 2025 am 12:01 AM

C和C 在JavaScript引擎中扮演了至关重要的角色,主要用于实现解释器和JIT编译器。1)C 用于解析JavaScript源码并生成抽象语法树。2)C 负责生成和执行字节码。3)C 实现JIT编译器,在运行时优化和编译热点代码,显著提高JavaScript的执行效率。

JavaScript在行動中:現實世界中的示例和項目JavaScript在行動中:現實世界中的示例和項目Apr 19, 2025 am 12:13 AM

JavaScript在現實世界中的應用包括前端和後端開發。 1)通過構建TODO列表應用展示前端應用,涉及DOM操作和事件處理。 2)通過Node.js和Express構建RESTfulAPI展示後端應用。

JavaScript和Web:核心功能和用例JavaScript和Web:核心功能和用例Apr 18, 2025 am 12:19 AM

JavaScript在Web開發中的主要用途包括客戶端交互、表單驗證和異步通信。 1)通過DOM操作實現動態內容更新和用戶交互;2)在用戶提交數據前進行客戶端驗證,提高用戶體驗;3)通過AJAX技術實現與服務器的無刷新通信。

了解JavaScript引擎:實施詳細信息了解JavaScript引擎:實施詳細信息Apr 17, 2025 am 12:05 AM

理解JavaScript引擎內部工作原理對開發者重要,因為它能幫助編寫更高效的代碼並理解性能瓶頸和優化策略。 1)引擎的工作流程包括解析、編譯和執行三個階段;2)執行過程中,引擎會進行動態優化,如內聯緩存和隱藏類;3)最佳實踐包括避免全局變量、優化循環、使用const和let,以及避免過度使用閉包。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

SecLists

SecLists

SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中

SublimeText3 英文版

SublimeText3 英文版

推薦:為Win版本,支援程式碼提示!

EditPlus 中文破解版

EditPlus 中文破解版

體積小,語法高亮,不支援程式碼提示功能