두 포인터 및 슬라이딩 창 패턴

패턴 1: 상수 창(창 = 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) 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