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

Minimum Size Subarray Sum · Nhóm: Cửa sổ trượt

Tìm đoạn con liên tiếp NGẮN NHẤT có tổng ≥ target, bằng cửa sổ trượt cộng dồn rồi thu ngắn.

Ý tưởng

Mở con trỏ phải R cộng dồn a[R] vào tổng cửa sổ.

Khi tổng ≥ target thì ghi lại độ dài, rồi thu con trỏ trái L (bớt a[L] khỏi tổng) để rút cửa sổ ngắn nhất còn hợp lệ, sau đó tiếp tục mở R.

Vì sao đúng

Cả L và R chỉ tiến một chiều nên mỗi phần tử được cộng vào và bớt ra tối đa một lần, tổng O(n); điều kiện tổng ≥ target được kiểm tra trong O(1) nên không phải quét lại các đoạn.

Mã Python

def min_size_subarray(a, target):
    n = len(a)
    best = n + 1            # length of shortest valid window
    s, L = 0, 0            # running sum and left edge
    for R in range(n):
        s += a[R]          # expand: add a[R]
        while s >= target:  # window is valid, try to shrink
            best = min(best, R - L + 1)
            s -= a[L]      # remove a[L]
            L += 1
    return best if best <= n else 0

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