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

兩個指針和滑動視窗模式

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

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]刪除
最新教學 更多>

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

Copyright© 2022 湘ICP备2022001581号-3