Chương trình đếm số danh sách con có tổng bằng mục tiêu trong Python

Mô tả bài toán

Cho danh sách số nums và giá trị target. Đếm số lượng danh sách con (sublist) liên tiếp có tổng bằng target.

Ví dụ: nums = [3, 0, 3], target = 3 → đầu ra 4 (các danh sách con: [3], [3,0], [0,3], [3]).

Giải thuật (Prefix Sum + Hash Map)

1. Khởi tạo temp là defaultdict(int), đặt temp[0] = 1.
2. s = 0, ans = 0.
3. Duyệt qua từng phần tử nums[i]:
   • s += nums[i].
   • comp = s - target.
   • Nếu comp có trong temp: ans += temp[comp].
   • temp[s] += 1.
4. Trả về ans.

Ví dụ mã Python

from collections import defaultdict

class Solution:
    def solve(self, nums, target):
        temp = defaultdict(int)
        temp[0] = 1
        s = 0
        ans = 0
        for i in range(len(nums)):
            s += nums[i]
            comp = s - target
            if comp in temp:
                ans += temp[comp]
            temp[s] += 1
        return ans

ob = Solution()
nums = [3, 0, 3]
target = 3
print(ob.solve(nums, target))

Đầu vào

[3, 0, 3], 3

Đầu ra

4