두 개의 포인터와 슬라이딩 윈도우 패턴

두 포인터 및 슬라이딩 윈도우 패턴

패턴 1: 상수 창(예: 창 = 4 또는 일부 정수 값)

예를 들어 (-ve 및 +ve) 정수 배열이 주어지면 크기가 k인 연속 창에 대한 최대 합계를 찾습니다.

패턴 2:(가변 창 크기) 예: 합계

• 접근 방식:
  • 무차별 대입: 가능한 모든 하위 배열을 생성하고 최대 길이 하위 배열을 선택합니다. sum <=k($O(n^2)$의 시간 복잡도를 갖습니다.
• 베팅/최적: 두 개의 포인터와 슬라이딩 윈도우를 사용하여 시간 복잡도를 O(n)으로 줄입니다.

패턴 3: sum=k와 같습니다.
이 문제는 확장할 때(오른쪽++), 축소할 때(왼쪽++) 어려워지기 때문에 해결하기가 매우 어렵습니다.

이 문제는 패턴 2
를 사용하여 해결할 수 있습니다. 합계가 k인 부분 문자열 수를 찾는 것과 같은 문제를 해결하는 데 사용됩니다.

• 다음과 같이 분류할 수 있습니다

  • sum
  • sum

패턴 4: 가장 짧은/최소 창 <조건>

패턴 2에 대한 다양한 접근 방식:
예: sum<=k
인 가장 큰 하위 배열

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




<p><strong>두 개의 포인터와 슬라이딩 창을 사용하는 더 나은 접근 방법</strong><br>
</p>

<pre class="brush:php;toolbar:false">        //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 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!