C++를 사용하여 주어진 범위에서 합계가 포함된 하위 배열의 수를 찾는 프로그램을 작성하세요.

이 기사에서는 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++를 사용하여 이 문제를 해결하는 두 가지 방법을 설명합니다. -

무차별 대입 방식

가장 기본적인 무차별 방식을 사용하여 각 계산을 수행합니다. sub 배열의 합계를 계산하고 그 합계가 주어진 범위 내에 있는지 여부를 찾습니다. (그러나 이 접근 방식은 시간 복잡도가 O(n*n)(여기서 n은 배열의 크기)이므로 많은 시간이 걸립니다.)

효율적인 방법

저장 이제 효율적인 방법은 슬라이딩 윈도우 기술을 사용하는 것입니다. 이 기술을 사용하면 O(n)에서 더 빠르고 효율적으로 결과를 계산할 수 있습니다.

Example

#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;
}

Output

3

위의 코드 설명

이 방법에서는 합이 주어진 범위의 상한보다 작은 하위 배열의 수를 세고 합이 해당 범위의 상한보다 작은 하위 배열의 수를 뺍니다. 주어진 범위의 상한보다 작습니다. 주어진 범위의 하한보다 작은 값을 얻으려면 subcount 함수를 사용하십시오.

Subcount 함수

이 함수는 슬라이딩 윈도우 기법을 사용하여 개수가 x보다 작은 하위 배열의 개수를 찾습니다.

먼저 "End"와 "Start"로 시작하며 둘 다 값이 0입니다. . 배열을 반복할 때 처음부터 끝까지 요소의 합을 유지합니다. 그 후, 시작이 끝과 같고 합계가 x보다 크거나 같으면 시작을 이동하기 시작하고 합계에서 요소를 제거하면서 합계를 계속 줄입니다.

합이 x보다 작아지거나 시작이 끝보다 커질 때까지. 이제 하위 배열 개수만큼 개수를 늘린 다음 오른쪽 경계를 1만큼 늘립니다. 이제 외부 루프가 끝난 후 하위 배열의 총 개수를 반환합니다.

결론

본 논문에서는 주어진 범위 내에 합이 포함되는 하위 배열의 개수를 O(n) 시간 복잡도로 구하는 문제를 슬라이딩 윈도우 기법을 이용하여 해결했습니다. 우리는 또한 C++ 프로그램을 통해 이 문제에 대해 배웠고 이를 쉽게(일반적으로 효율적으로) 해결할 수 있는 완전한 방법을 배웠습니다. C, java, python 등과 같은 다른 언어로도 동일한 프로그램을 작성할 수 있습니다.

위 내용은 C++를 사용하여 주어진 범위에서 합계가 포함된 하위 배열의 수를 찾는 프로그램을 작성하세요.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!