C++ Số mảng con có tổng trong khoảng cho trước

Cho mảng số dương và khoảng [L,R]. Đếm mảng con có tổng trong [L,R]. Ví dụ:

Input: {1,4,6}, L=3, R=8 → Output: 3 ({1,4}, {4}, {6})
Input: {2,3,5,8}, L=4, R=13 → Output: 6 ({2,3}, {2,3,5}, {3,5}, {5}, {5,8}, {8})

Phương pháp

Vét cạn

Tính tổng mọi mảng con, kiểm tra trong khoảng. O(n²).

Hiệu quả: Cửa sổ trượt

Đếm mảng con tổng ≤ R trừ mảng con tổng ≤ L-1. Hàm subCount(x) đếm mảng con tổng < x bằng sliding window O(n).

Ví dụ minh họa

#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 += arr[end];
        while (start <= end && sum >= x) {
            sum -= arr[start];
            start++;
        }
        count += (end - start + 1);
        end++;
    }
    return count;
}

int main() {
    int arr[] = {1,4,6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int L=3, R=8;
    int ans = subCount(arr, n, R) - subCount(arr, n, L-1);
    cout << ans << "\n";
    return 0;
}

Kết quả

3

Giải thích subCount

Mở rộng end, thu hẹp start khi sum ≥ x. Số mảng con kết thúc tại end có tổng < x là (end-start+1).

Kết luận

Đếm mảng con tổng trong [L,R] = subCount(R) - subCount(L-1) bằng sliding window O(n). Code C++ áp dụng cho C, Java, Python. Hy vọng hữu ích.