Mô phỏng thuật toán Đoạn con ngắn nhất ≥ S

Smallest Subarray ≥ S · Nhóm: Cửa sổ trượt

Đoạn con ngắn nhất ≥ S (Smallest Subarray ≥ S), nhóm Cửa sổ trượt.

Mã Python

def min_subarray(a, S):
    lo = 0
    total = 0
    best = len(a) + 1
    for hi in range(len(a)):
        total += a[hi]
        while total >= S:
            best = min(best, hi - lo + 1)
            total -= a[lo]
            lo += 1
    return best if best <= len(a) else 0

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.