Trong bài viết này, chúng tôi sẽ giải quyết số lượng các mảng con có tổng trong một phạm vi nhất định bằng cách sử dụng chương trình C ++. Chúng ta có một mảng arr [] các số nguyên dương và một dải ô {L, R} và chúng ta phải tính tổng số mảng con có tổng ở dạng dải ô đã cho từ L đến R. Vì vậy, đây là ví dụ đơn giản cho vấn đề:
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}. Phương pháp tiếp cận để tìm giải pháp
Chúng tôi sẽ giải thích hai phương pháp để giải quyết vấn đề này bằng cách sử dụng các bài toán C ++ -
Phương pháp tiếp cận vũ phu
Cách tiếp cận brute force cơ bản nhất được sử dụng để tính tổng của mọi mảng con và sau đó tìm xem tổng đó có tồn tại trong phạm vi đã cho hay không. (Nhưng cách làm này sẽ khiến chúng ta tốn rất nhiều thời gian vì độ phức tạp về thời gian của nó là O (n * n) trong đó n là kích thước của mảng).
Cách tiếp cận hiệu quả
Để tiết kiệm thời gian, chúng tôi sử dụng một phương pháp khác được gọi là phương pháp hiệu quả. Bây giờ phương pháp hiệu quả là sử dụng kỹ thuật cửa sổ trượt, sử dụng kỹ thuật này, chúng tôi sẽ tính toán kết quả của mình nhanh hơn hoặc hiệu quả hơn nhiều trong O (n).
Ví dụ
#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;
} Đầu ra
3
Giải thích về Quy tắc trên
Trong cách tiếp cận này, chúng tôi đang đếm số lượng mảng con có tổng nhỏ hơn giới hạn trên của dải ô đã cho, và sau đó chúng tôi sẽ trừ số lượng mảng con có tổng nhỏ hơn giới hạn dưới của dải ô đã cho bằng cách sử dụng hàm số con của chúng tôi.
Hàm số phụ
Hàm này sử dụng kỹ thuật cửa sổ trượt để tìm số lượng các mảng con có số lượng nhỏ hơn x.
Lúc đầu, chúng tôi bắt đầu với cả 'kết thúc và bắt đầu' với 0 là giá trị của chúng. Khi chúng ta duyệt qua mảng, chúng ta duy trì tổng các phần tử từ đầu đến cuối. Sau đó, nếu số bắt đầu của chúng tôi bằng số cuối của chúng tôi và tổng lớn hơn hoặc bằng x, chúng tôi bắt đầu di chuyển số bắt đầu của mình và tiếp tục giảm tổng khi chúng tôi loại bỏ các phần tử khỏi tổng.
Cho đến khi tổng của chúng tôi trở nên nhỏ hơn x hoặc phần đầu của chúng tôi lớn hơn phần cuối. Bây giờ chúng ta tăng số đếm bằng số mảng con và sau đó tăng đường viền bên phải bằng 1. Bây giờ, sau khi vòng lặp bên ngoài của chúng ta kết thúc, chúng ta trả về tổng số các mảng con của chúng ta.
Kết luận
Trong bài viết này, chúng tôi giải quyết một vấn đề để tìm số lượng các mảng con có tổng trong một phạm vi nhất định với độ phức tạp thời gian O (n) bằng cách sử dụng kỹ thuật cửa sổ trượt. Chúng tôi cũng đã học được từ chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi có thể giải quyết vấn đề này một cách dễ dàng. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python, v.v.