Chương trình tìm số lượng subarray không chồng chéo tối đa có sum bằng target bằng Python

Cho mảng nums và target. Tìm số lượng subarray không rỗng, không chồng chéo tối đa mà tổng mỗi subarray = target.

Ví dụ: nums=[3,2,4,5,2,1,5], target=6 → 2 subarray: [2,4] và [1,5].

Thuật toán

• t = {0}, temp=0, ans=0
• Duyệt i trong nums:
  • temp += i
  • prev = temp - target
  • Nếu prev trong t: ans += 1; t = {temp} (reset)
  • Ngược lại: t.add(temp)
• Return ans

Code Python

def solve(nums, target):
    t = {0}
    temp = 0
    ans = 0
    for i in nums:
        temp += i
        prev = temp - target
        if prev in t:
            ans += 1
            t = {temp}
        else:
            t.add(temp)
    return ans

nums = [3,2,4,5,2,1,5]
target = 6
print(solve(nums, target))

Input

[3,2,4,5,2,1,5], 6

Output

2