兩個指針和滑動視窗模式

雙指針與滑動視窗模式

模式 1：常數視窗（如 window = 4 或某個整數值）

例如，給定一個 (-ve 和 +ve) 整數數組，找到大小為 k.

的連續視窗的最大總和

模式 2：（可變視窗大小）具有 的最大子數組/子字串範例：總和

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

模式 3： 的子陣列/子字串的數量就像 sum=k。
這個問題很難解決，因為何時擴展（右++）或何時收縮（左++）變得困難。

這個問題可以用模式2
解決 用於解決諸如查找 sum =k 的子串數量之類的問題。

• 這可以分解為

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

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

模式 2 的不同方法：
例：總和
的最大子數組

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
        //tc : O(n^2)
        int maxlen=0;
        for(int i =0;i<arr.length;i++){
            int sum =0;
            for(int j = i+1;j<arr.length;j++){
                sum+=arr[j];
                if(sum<=k){
                    maxLen = Integer.max(maxLen, j-i+1);
                }
                else if(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<arr.length){
            sum+=arr[right];
            while(sum > k){
                sum = sum-arr[left];
                left++;
            }
            if(sum <=k){
                maxLen = Integer.max(maxLen, right-left+1); //if asked to print max subarray length,we print maxLen else asked for printing the subarray keep track of
                // left and right in a different variable 
            }
            right++;
        }

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

當子數組不滿足條件 (<=k)int left = 0 時，最佳方法是僅在子數組長度大於 maxLen 時收縮左側。

        int right =0;
        int sum = 0;
        int maxLen = 0;
        while(right<arr.length){
            sum+=arr[right];
            if(sum > k){// this will ensure that the left is incremented one by one (not till the sum<=k because this might reduce the length i.e right-left+1  which will not be taken into consideration)
                sum = sum-arr[left];
                left++;
            }
            if(sum <=k){
                maxLen = Integer.max(maxLen, right-left+1); //if asked to print max subarray length,we print maxLen else asked for printing the subarray keep track of
                // left and right in a different variable 
            }
            right++;
        }

    }
}

以上是兩個指針和滑動視窗模式的詳細內容。更多資訊請關注PHP中文網其他相關文章！