이 기사에서는 C++ 프로그램을 사용하여 주어진 범위에서 합을 갖는 하위 배열의 수를 풉니다. 우리는 양의 정수로 구성된 배열 arr[]와 {L, R} 범위를 가지고 있으며 주어진 범위 형식 L에서 R에서 합계를 갖는 하위 배열의 총 수를 계산해야 합니다. 그래서 여기에 문제에 대한 간단한 예가 있습니다.
Input : arr[] = {1, 4, 6}, L = 3, R = 8
Output : 3
The subarrays are {1, 4}, {4}, {6}.
Input : arr[] = {2, 3, 5, 8}, L = 4, R = 13
Output : 6
The subarrays are {2, 3}, {2, 3, 5}, {3, 5},
{5}, {5, 8}, {8}. 해결책을 찾기 위한 접근 방식
우리는 C++ 문제를 사용하여 이 문제를 해결하는 두 가지 방법을 설명할 것입니다 -
무차별 대입 접근
가장 기본적인 무차별 대입 접근 방식은 모든 하위 배열의 합계를 계산한 다음 해당 합계가 지정된 범위에 있는지 여부를 찾는 데 사용됩니다. (하지만 이 접근 방식은 시간 복잡도가 O(n*n)이고 n이 배열의 크기이기 때문에 많은 시간이 소요됩니다.)
효율적인 접근
시간을 절약하기 위해 효율적인 접근 방식으로 알려진 다른 방법을 사용합니다. 이제 효율적인 접근 방식은 슬라이딩 윈도우 기술을 사용하는 것입니다. 이 기술을 사용하면 O(n)에서 훨씬 빠르고 효율적으로 결과를 계산할 수 있습니다.
예
#include <bits/stdc++.h>
using namespace std;
int subCount(int *arr, int n, int x){
int start = 0, end = 0, sum = 0, count = 0;
while (end < n){ // we will be moving right border in this loop
sum = sum + arr[end];
while(start <= end && sum >= x){ // this loop will move our left border
sum = sum - arr[start]; // we will decrement sum while moving left border.
// For excluding the previous elements.
start++; // and move the left border.
}
count = count + ((end - start) + 1); // counting the subarrays.
end++;
}
return count;
}
int main(){
int arr[] = { 1, 4, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int L = 3;
int R = 8;
int answer;
answer = subCount(arr, n, R) - subCount(arr, n, (L - 1)); // Final Answer.
cout << answer << "\n";
return 0;
} 출력
3
위 코드 설명
이 접근 방식에서는 합이 주어진 범위의 상한보다 작은 하위 배열의 수를 세고 하위 카운트 함수를 사용하여 합이 주어진 범위의 하한보다 작은 하위 배열의 수를 뺍니다.
하위 계산 기능
이 함수는 카운트가 x보다 작은 하위 배열의 카운트를 찾기 위해 슬라이딩 윈도우 기술을 사용합니다.
처음에는 0을 값으로 하는 '끝과 시작'으로 시작합니다. 배열을 탐색할 때 처음부터 끝까지 요소의 합을 유지합니다. 그 후, 시작이 끝과 같고 합이 x보다 크거나 같으면 시작을 움직이기 시작하고 합에서 요소를 제거하면서 합을 계속 감소시킵니다.
합이 x보다 작아지거나 시작이 끝보다 커질 때까지. 이제 하위 배열 개수만큼 개수를 증가시킨 다음 오른쪽 경계를 1로 증가시킵니다. 이제 외부 루프가 끝난 후 하위 배열의 총 개수를 반환합니다.
결론
이 기사에서는 슬라이딩 윈도우 기법을 사용하여 O(n) 시간 복잡도에서 주어진 범위에서 합을 갖는 하위 배열의 수를 찾는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 쉽게 해결할 수 있는 완전한 접근 방식(보통 및 효율적)을 배웠습니다. C, Java, python 등과 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다.