Chương trình tìm độ dài dãy con nhỏ nhất có tổng ít nhất target trong Python

Cho danh sách nums và target. Tìm độ dài dãy con liên tiếp (sublist) ngắn nhất có tổng ≥ target. Trả về -1 nếu không có.

Ví dụ: nums=[2,11,-4,17,4], target=19 → 2 (dãy [17,4]).

Giải pháp

Prefix sum + Monotonic Queue (deque):

• ps[i] = prefix sum đến i
• Duyệt i từ 1 đến n, duy trì deque q các chỉ số với ps tăng dần
• Với mỗi i: tìm j nhỏ nhất trong q sao cho ps[i] - ps[j] ≥ target (binary search hoặc two pointers)
• Cập nhật min_size = min(min_size, i - j)
• Giữ deque đơn điệu: pop right khi ps[i] ≤ ps[q[-1]]

Ví dụ minh họa

class Solution:
    def solve(self, nums, target):
        ps = [0]
        for num in nums:
            ps += [ps[-1] + num]
            if num >= target:
                return 1
        min_size = float("inf")
        q = [0]
        j = 0
        for i in range(1, len(ps)):
            j = min(j, len(q) - 1)
            while j < len(q) and ps[i] - ps[q[j]] >= target:
                min_size = min(min_size, i - q[j])
                j += 1
            while q and ps[i] <= ps[q[-1]]:
                q.pop()
            q.append(i)
        return min_size if min_size < float("inf") else -1

ob = Solution()
nums = [2, 11, -4, 17, 4]
target = 19
print(ob.solve(nums, target))

Đầu vào

[2, 11, -4, 17, 4], 19

Đầu ra

2