Chương trình đếm dãy con có tổng bằng k trong mảng nhị phân Python

Cho mảng nhị phân nums (chỉ chứa 0 và 1) và số k. Đếm số dãy con liên tiếp có tổng bằng k.

Ví dụ: nums=[1,0,0,1,1,1,0,1], k=3 → 8 dãy con.

Giải thuật (Tiền tố + Hash map)

1. sums lưu tần suất các tổng tiền tố (khởi tạo sums[0]=1)
2. Duyệt mảng, cập nhật r_sum (tổng tiền tố)
3. Số dãy con kết thúc tại vị trí hiện tại có tổng k = sums[r_sum - k]
4. Cập nhật sums[r_sum]

Ví dụ triển khai

def solve(nums, k):
    sums = {0: 1}
    r_sum = 0
    ans = 0
    for x in nums:
        r_sum += x
        ans += sums.get(r_sum - k, 0)
        sums[r_sum] = sums.get(r_sum, 0) + 1
    return ans

print(solve([1, 0, 0, 1, 1, 1, 0, 1], 3))

Đầu vào

[1, 0, 0, 1, 1, 1, 0, 1], 3

Đầu ra

8