Trong bài viết này, chúng ta sẽ tìm hiểu cách xác định số lượng mảng con (subarray) có tổng nhỏ hơn K bằng ngôn ngữ C++. Bài toán cho một mảng arr[] và một số nguyên K, yêu cầu đếm các mảng con mà tổng các phần tử nhỏ hơn K. Ví dụ minh họa:
Input : arr[] = {1, 11, 2, 3, 15} K = 10 Output : 4 {1}, {2}, {3} và {2, 3}
Các phương pháp giải quyết
Chúng ta sẽ trình bày hai phương pháp khác nhau để giải quyết bài toán này:
1. Phương pháp Brute Force (Thử tất cả)
Cách tiếp cận này duyệt qua tất cả các mảng con có thể, tính tổng của từng mảng con và so sánh với K. Nếu tổng nhỏ hơn K, tăng biến đếm kết quả.
Ví dụ mã nguồn
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {1, 11, 2, 3, 15}; // mảng cho trước
int k = 10; // giá trị K
int size = sizeof(arr) / sizeof(int); // kích thước mảng
int ans = 0; // biến đếm kết quả
for (int i = 0; i < size; i++) { // vòng lặp ngoài
int sum = 0;
for (int j = i; j < size; j++) { // vòng lặp trong
sum = sum + arr[j];
if (sum < k) // so sánh với K
ans++; // tăng ans nếu tổng < K
}
}
cout << ans << "\n";
return 0;
}
Kết quả
4
Tuy nhiên, phương pháp này không hiệu quả do độ phức tạp thời gian cao là O(N²), với N là kích thước mảng.
Chúng ta sẽ xem xét giải pháp thay thế sử dụng kỹ thuật Sliding Window (Cửa sổ trượt) để giảm độ phức tạp thời gian.
2. Phương pháp hiệu quả (Sliding Window)
Khác với Brute Force, chúng ta không duyệt qua tất cả mảng con. Thay vào đó, ta duy trì một cửa sổ trượt: mở rộng cửa sổ bằng cách dịch chuyển biên phải, và khi tổng vượt quá hoặc bằng K, thu hẹp cửa sổ bằng cách dịch chuyển biên trái cho đến khi tổng lại nhỏ hơn K. Quá trình lặp lại cho đến khi duyệt hết mảng.
Ví dụ mã nguồn
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {1, 11, 2, 3, 15};
int k = 10;
int size = sizeof(arr) / sizeof(int);
int ans = 0;
int start = 0; // biên trái
int end = 0; // biên phải
int sum = 0;
while (end < size && start < size) {
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;
}
Kết quả
4
Giải thích mã nguồn
Trong phương pháp này, ta duyệt mảng bình thường khi tổng nhỏ hơn K và cập nhật kết quả. Điểm quan trọng xảy ra khi tổng lớn hơn hoặc bằng K: lúc này ta dịch chuyển biên trái (start) về phía phải, trừ đi các phần tử tương ứng khỏi tổng, cho đến khi tổng lại nhỏ hơn K hoặc start vượt quá end. Mỗi lần mở rộng biên phải, số mảng con hợp lệ kết thúc tại end chính là end - start, ta cộng vào kết quả.
Độ phức tạp thời gian của phương pháp này là O(N), hiệu quả hơn đáng kể so với O(N²) của Brute Force, đặc biệt với mảng lớn.
Kết luận
Bài viết đã giải quyết bài toán đếm mảng con có tổng nhỏ hơn K bằng kỹ thuật Sliding Window. Chúng ta đã trình bày cả hai cách tiếp cận (thông thường và tối ưu) cùng mã nguồn C++ hoàn chỉnh. Cùng giải thuật có thể triển khai bằng C, Java, Python và các ngôn ngữ khác. Hy vọng bài viết hữu ích cho bạn.