」工欲善其事,必先利其器。「—孔子《論語.錄靈公》
首頁 > 程式設計 > 兩個指針和滑動視窗模式

兩個指針和滑動視窗模式

發佈於2024-11-09
瀏覽:853

Two Pointer and sliding window pattern

雙指標與滑動視窗模式

模式1:常數視窗(如window = 4或某個整數值)

例如,給定一個(-ve 和 ve)整數數組,找到大小為 k 的連續視窗的最大和.

模式2:(可變視窗大小)具有的最大子數組/子字串範例:sum

  • 方法:
    • 蠻力: 產生所有可能的子數組並選擇最大長度的子數組 sum
  • 最佳/最佳: 利用兩個指標和滑動視窗將時間複雜度降低到O(n)

模式3:子數組/子字串的數量,其中像sum=k。
這個問題很難解決,因為何時擴展(右)或何時收縮(左)變得很困難。

這個問題可以用模式2
來解決 用於解決諸如查找 sum =k.

的子串數量之類的問題
  • 這可以細分為

    • 找出 sum 的子數組
    • 找出sum

模式4:找出最短/最小視窗

模式 2 的不同方法
範例:sum

public class Sample{
    public static void main(String args[]){
        n = 10;
        int arr[] = new int[n];

        //Brute force approach for finding the longest subarray with sum  k) break; /// optimization if the sum is greater than the k, what is the point in going forward? 
            }
        }

使用兩個指標和滑動視窗的更好方法

        //O(n n) in the worst case r will move from 0 to n and in the worst case left will move from 0 0 n as well so 2n
        int left = 0;
        int right =0;
        int sum = 0;
        int maxLen = 0;
        while(right k){
                sum = sum-arr[left];
                left  ;
            }
            if(sum 



最佳方法
我們知道,如果找到子數組,我們將其長度儲存在maxLen 中,但是在添加arr[right] 時,如果總和大於k,那麼當前我們透過執行sum = sum-arr[left] 和left 來向左收縮。
我們知道目前的最大長度是maxLen,如果我們繼續縮小左索引,我們可能會得到另一個滿足條件( maxLen 的子數組,則僅更新maxLen。

當子數組不滿足條件 (

        int right =0;
        int sum = 0;
        int maxLen = 0;
        while(right k){// this will ensure that the left is incremented one by one (not till the sum




          

            
  

            
        
版本聲明 本文轉載於:https://dev.to/prashantrmishra/two-pointer-and-sliding-window-pattern-4118?1如有侵犯,請洽[email protected]刪除
最新教學 更多>
  • 為什麼不````''{margin:0; }`始終刪除CSS中的最高邊距?
    為什麼不````''{margin:0; }`始終刪除CSS中的最高邊距?
    在CSS 問題:不正確的代碼: 全球範圍將所有餘量重置為零,如提供的代碼所建議的,可能會導致意外的副作用。解決特定的保證金問題是更建議的。 例如,在提供的示例中,將以下代碼添加到CSS中,將解決餘量問題: body H1 { 保證金頂:-40px; } 此方法更精確,避免了由全局保證金重置...
    程式設計 發佈於2025-06-09
  • 在程序退出之前,我需要在C ++中明確刪除堆的堆分配嗎?
    在程序退出之前,我需要在C ++中明確刪除堆的堆分配嗎?
    在C中的顯式刪除 在C中的動態內存分配時,開發人員通常會想知道是否需要手動調用“ delete”操作員在heap-exprogal exit exit上。本文深入研究了這個主題。 在C主函數中,使用了動態分配變量(HEAP內存)的指針。當應用程序退出時,此內存是否會自動發布?通常,是。但是,即使在...
    程式設計 發佈於2025-06-09
  • 如何限制動態大小的父元素中元素的滾動範圍?
    如何限制動態大小的父元素中元素的滾動範圍?
    在交互式接口中實現垂直滾動元素的CSS高度限制,控制元素的滾動行為對於確保用戶體驗和可訪問性是必不可少的。一種這樣的方案涉及限制動態大小的父元素中元素的滾動範圍。 問題:考慮一個佈局,其中我們具有與用戶垂直滾動一起移動的可滾動地圖div,同時與固定的固定sidebar保持一致。但是,地圖的滾動無限...
    程式設計 發佈於2025-06-09
  • 可以在純CS中將多個粘性元素彼此堆疊在一起嗎?
    可以在純CS中將多個粘性元素彼此堆疊在一起嗎?
    [2这里: https://webthemez.com/demo/sticky-multi-header-scroll/index.html </main> <section> { display:grid; grid-template-...
    程式設計 發佈於2025-06-09
  • 如何同步迭代並從PHP中的兩個等級陣列打印值?
    如何同步迭代並從PHP中的兩個等級陣列打印值?
    同步的迭代和打印值來自相同大小的兩個數組使用兩個數組相等大小的selectbox時,一個包含country代碼的數組,另一個包含鄉村代碼,另一個包含其相應名稱的數組,可能會因不當提供了exply for for for the uncore for the forsion for for ytry...
    程式設計 發佈於2025-06-09
  • 如何檢查對像是否具有Python中的特定屬性?
    如何檢查對像是否具有Python中的特定屬性?
    方法來確定對象屬性存在尋求一種方法來驗證對像中特定屬性的存在。考慮以下示例,其中嘗試訪問不確定屬性會引起錯誤: >>> a = someClass() >>> A.property Trackback(最近的最新電話): 文件“ ”,第1行, AttributeError: SomeClass...
    程式設計 發佈於2025-06-09
  • Android如何向PHP服務器發送POST數據?
    Android如何向PHP服務器發送POST數據?
    在android apache httpclient(已棄用) httpclient httpclient = new defaulthttpclient(); httppost httppost = new httppost(“ http://www.yoursite.com/script.p...
    程式設計 發佈於2025-06-09
  • 為什麼儘管有效代碼,為什麼在PHP中捕獲輸入?
    為什麼儘管有效代碼,為什麼在PHP中捕獲輸入?
    在php ;?>" method="post">The intention is to capture the input from the text box and display it when the submit button is clicked.但是,輸出...
    程式設計 發佈於2025-06-09
  • 如何使用替換指令在GO MOD中解析模塊路徑差異?
    如何使用替換指令在GO MOD中解析模塊路徑差異?
    在使用GO MOD時,在GO MOD 中克服模塊路徑差異時,可能會遇到衝突,其中3個Party Package將另一個PAXPANCE帶有導入式套件之間的另一個軟件包,並在導入式套件之間導入另一個軟件包。如迴聲消息所證明的那樣: go.etcd.io/bbolt [&&&&&&&&&&&&&&&&...
    程式設計 發佈於2025-06-09
  • 為什麼PYTZ最初顯示出意外的時區偏移?
    為什麼PYTZ最初顯示出意外的時區偏移?
    與pytz 最初從pytz獲得特定的偏移。例如,亞洲/hong_kong最初顯示一個七個小時37分鐘的偏移: 差異源利用本地化將時區分配給日期,使用了適當的時區名稱和偏移量。但是,直接使用DateTime構造器分配時區不允許進行正確的調整。 example pytz.timezone(&#...
    程式設計 發佈於2025-06-09
  • Java的Map.Entry和SimpleEntry如何簡化鍵值對管理?
    Java的Map.Entry和SimpleEntry如何簡化鍵值對管理?
    的綜合集合:在Java中介紹Java的Map.entry和SimpleEntry和SimpleEntry和SimpleEntry和SimpleEntry和SimpleEntry和SimpleEntry和SimpleEntry和SimpleEntry apry and Map。 地圖。它具有兩個通用...
    程式設計 發佈於2025-06-09
  • 如何使用FormData()處理多個文件上傳?
    如何使用FormData()處理多個文件上傳?
    )處理多個文件輸入時,通常需要處理多個文件上傳時,通常是必要的。 The fd.append("fileToUpload[]", files[x]); method can be used for this purpose, allowing you to send multi...
    程式設計 發佈於2025-06-09
  • Go語言垃圾回收如何處理切片內存?
    Go語言垃圾回收如何處理切片內存?
    Garbage Collection in Go Slices: A Detailed AnalysisIn Go, a slice is a dynamic array that references an underlying array.使用切片時,了解垃圾收集行為至關重要,以避免潛在的內存洩...
    程式設計 發佈於2025-06-09
  • 對象擬合:IE和Edge中的封面失敗,如何修復?
    對象擬合:IE和Edge中的封面失敗,如何修復?
    To resolve this issue, we employ a clever CSS solution that solves the problem:position: absolute;top: 50%;left: 50%;transform: translate(-50%, -50%)...
    程式設計 發佈於2025-06-09
  • Java中假喚醒真的會發生嗎?
    Java中假喚醒真的會發生嗎?
    在Java中的浪費喚醒:真實性或神話? 在Java同步中偽裝喚醒的概念已經是討論的主題。儘管存在這種行為的潛力,但問題仍然存在:它們實際上是在實踐中發生的嗎? Linux的喚醒機制根據Wikipedia關於偽造喚醒的文章,linux實現了pthread_cond_wait()功能的Linux實現,...
    程式設計 發佈於2025-06-09

免責聲明: 提供的所有資源部分來自互聯網,如果有侵犯您的版權或其他權益,請說明詳細緣由並提供版權或權益證明然後發到郵箱:[email protected] 我們會在第一時間內為您處理。

Copyright© 2022 湘ICP备2022001581号-3