Tìm số lượng mảng con có tổng trong khoảng cho trước bằng C++

Trong bài viết này, chúng ta sẽ giải quyết bài toán đếm số mảng con có tổng nằm trong khoảng [L, R] bằng C++. Cho mảng arr[] gồm các số nguyên dương và một khoảng {L, R}, nhiệm vụ là tính tổng số mảng con có tổng từ L đến R. Ví dụ minh họa:

Input : arr[] = {1, 4, 6}, L = 3, R = 8 Output : 3 Các mảng con: {1, 4}, {4}, {6}
Input : arr[] = {2, 3, 5, 8}, L = 4, R = 13 Output : 6 Các mảng con: {2, 3}, {2, 3, 5}, {3, 5}, {5}, {5, 8}, {8}

Các phương pháp giải quyết

Chúng ta sẽ trình bày hai phương pháp:

1. Phương pháp Brute Force

Cách cơ bản nhất là tính tổng của mọi mảng con và kiểm tra xem tổng đó có nằm trong khoảng [L, R] hay không. Tuy nhiên, độ phức tạp thời gian là O(N²), không phù hợp với dữ liệu lớn.

2. Phương pháp hiệu quả (Sliding Window)

Để tối ưu, ta sử dụng kỹ thuật Sliding Window, cho phép giải quyết trong O(N). Ý tưởng cốt lõi: số mảng con có tổng trong [L, R] = (số mảng con có tổng ≤ R) - (số mảng con có tổng ≤ L-1).

Ví dụ mã nguồ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) {
        sum = sum + arr[end];
        while (start <= end && sum >= x) {
            sum = sum - arr[start];
            start++;
        }
        count = count + ((end - start) + 1);
        end++;
    }
    return count;
}

int main() {
    int n, L, R;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    cin >> L >> R;
    int answer = subCount(arr, n, R) - subCount(arr, n, (L - 1));
    cout << answer << "\n";
    return 0;
}

Kết quả

1

Giải thích mã nguồn

Hàm subCount sử dụng Sliding Window để đếm số mảng con có tổng nhỏ hơn x. Ta duy trì hai con trỏ start và end cùng biến sum lưu tổng cửa sổ hiện tại. Khi sum >= x, thu hẹp cửa sổ từ bên trái. Số mảng con kết thúc tại end và có tổng < x là end - start + 1.

Trong main, kết quả cuối cùng là hiệu giữa số mảng con tổng ≤ R và số mảng con tổng ≤ L-1.

Kết luận

Bài viết đã giải quyết bài toán đếm mảng con có tổng trong khoảng [L, R] với độ phức tạp O(N) nhờ Sliding Window. Mã nguồn C++ đầy đủ và giải thích chi tiết đã được trình bày. Giải thuật này có thể triển khai bằng C, Java, Python và các ngôn ngữ khác.