Trong bài này, chúng ta sẽ tìm hiểu số lượng các mảng con có tổng nhỏ hơn K bằng cách sử dụng C ++. Trong bài toán này, chúng ta có một mảng arr [] và một số nguyên K. Vì vậy, bây giờ chúng ta phải tìm các mảng con có tổng nhỏ hơn K. Đây là ví dụ -
Input : arr[] = {1, 11, 2, 3, 15}
K = 10
Output : 4
{1}, {2}, {3} and {2, 3} Phương pháp tiếp cận để tìm giải pháp
Bây giờ chúng ta sẽ sử dụng hai phương pháp khác nhau để giải quyết vấn đề đã cho -
Lực lượng vũ phu
Trong cách tiếp cận này, chúng tôi sẽ lặp lại qua tất cả các mảng con và tính tổng của chúng và so sánh với k nếu tổng nhỏ hơn k để tăng câu trả lời của chúng tôi.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // given array
int k = 10; // given k
int size = sizeof(arr) / sizeof(int); // size of our array.
int ans = 0; // counter variable.
for(int i = 0; i < size; i++){ // outer loop.
int sum = 0;
for(int j = i; j < size; j++){ // inner loop.
sum = sum + arr[j];
if(sum < k) // comparing with k.
ans++; // incrementing our ans if sum is less than k.
}
}
cout << ans << "\n";
return 0;
} Đầu ra
4
Tuy nhiên, cách làm này không tốt lắm vì độ phức tạp về thời gian là rất cao O (N * N) , trong đó n là kích thước mảng của chúng ta.
Chúng tôi sẽ xem xét một giải pháp thay thế bằng phương pháp Cửa sổ trượt (Điều đó sẽ giúp chúng tôi giảm độ phức tạp về thời gian của chương trình).
Phương pháp tiếp cận hiệu quả
Không giống như Lực lượng vũ phu , chúng tôi sẽ không đi qua tất cả các phân vùng con. Thay vào đó, chúng ta sẽ chỉ duyệt khi tổng của một mảng con vượt quá k và di chuyển đường viền bên trái sang đường viền bên phải của chúng ta và tiếp tục lặp lại cho đến khi toàn bộ mảng được duyệt qua.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // given array
int k = 10; // given k
int size = sizeof(arr) / sizeof(int); // size of our array.
int ans = 0; // counter variable.
int start = 0; // left border.
int end = 0; // right border.
int sum = 0;
while(end < size && start < size){ // till the whole array is traversed.
while(sum >= k && start < end){
sum = sum - arr[start];
start++;
}
if(end >= start)
ans = ans + end - start;
sum += arr[end];
end++;
}
cout << ans << "\n";
return 0;
} Đầu ra
4
Chúng tôi sử dụng Kỹ thuật cửa sổ trượt để làm cho chương trình của chúng tôi chạy nhanh hơn hoặc tiết kiệm thời gian hơn vì những hạn chế lớn hơn trong cách tiếp cận này.
Giải thích về Quy tắc trên
Trong cách tiếp cận này, chúng tôi thường duyệt cho đến khi tổng của chúng tôi nhỏ hơn k và tăng câu trả lời của chúng tôi theo nó bây giờ là sự thay đổi quan trọng trong mã xảy ra khi tổng trở nên lớn hơn hoặc bằng k. Trong tình huống này, chúng ta bắt đầu tăng đường viền bên trái nhỏ hơn đường viền bên phải hoặc cho đến khi tổng lớn hơn hoặc bằng k. Khi chúng tôi xử lý thêm, nó đi ngang qua các phân vùng con khác có thể được hình thành. Các mảng con mới này có tổng nhỏ hơn k được thêm vào câu trả lời của chúng tôi, vì vậy câu trả lời của chúng tôi sẽ tăng lên.
Cách tiếp cận này rất hiệu quả so với Lực lượng vũ phu trước đó chúng tôi đã áp dụng vì độ phức tạp về thời gian của nó là O (N) , trong đó N là kích thước mảng của chúng ta.
Kết luận
Trong bài viết này, chúng tôi giải quyết vấn đề để tìm Số lượng mảng con có tổng nhỏ hơn k bằng cách sử dụng Kỹ thuật cửa sổ trượt . Chúng tôi cũng đã học 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 đã giải quyết vấn đề này. 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à các ngôn ngữ khác. Hy vọng bạn thấy bài viết này hữu ích.