2 つのポインターとスライディング ウィンドウのパターン

ツーポインターおよびスライディング ウィンドウのパターン

パターン 1: 定数ウィンドウ (window = 4 または何らかの整数値など)

たとえば、(-ve および +ve) の整数の配列が与えられた場合、サイズ k の連続ウィンドウの最大合計を見つけます.

パターン 2:(可変ウィンドウ サイズ) を持つ最大の部分配列/部分文字列例: 合計

• アプローチ:
  • ブルートフォース: 考えられるすべての部分配列を生成し、最大長の部分配列を選択します 合計
• 優れた/最適: 2 つのポインターとスライディング ウィンドウを利用して、時間の複雑さを O(n) に削減します。

パターン 3: が指定される部分配列/部分文字列の数sum=k のように。
これを解決するのは非常に困難です。なぜなら、いつ拡大するか (右++)、いつ縮小するか (左++) かが難しくなるためです。

この問題は、パターン 2
を使用して解決できます。 sum =k.

となる部分文字列の数を見つけるなどの問題を解決するため。

• これは次のように分解できます

  • 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
        //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? 
            }
        }

2 つのポインターとスライディング ウィンドウを使用したより良いアプローチ

        //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++ を実行することで左に縮小しています。
現在の Max 長さが 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++;
        }

    }
}

以上が2 つのポインターとスライディング ウィンドウのパターンの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。