두 포인터 및 슬라이딩 윈도우 패턴
패턴 1: 상수 창(예: 창 = 4 또는 일부 정수 값)
예를 들어 (-ve 및 +ve) 정수 배열이 주어지면 크기가 k인 연속 창에 대한 최대 합계를 찾습니다.
패턴 2:(가변 창 크기)
패턴 3:
이 문제는 확장할 때(오른쪽++), 축소할 때(왼쪽++) 어려워지기 때문에 해결하기가 매우 어렵습니다.
이 문제는 패턴 2
를 사용하여 해결할 수 있습니다.
합계가 k인 부분 문자열 수를 찾는 것과 같은 문제를 해결하는 데 사용됩니다.
다음과 같이 분류할 수 있습니다
패턴 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(rightk){// 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!