Hai con trỏ & Cửa sổ trượtTwo Pointers & Sliding Window

Thuộc bộ kiến thức Data Structures & Algorithms Roadmap.

Tổng quan

Các pattern trong bài này đều chung một lập luận kinh tế: thay một vòng lặp lồng nhau bằng một cặp chỉ số mà mỗi cái chỉ tiến về phía trước. Vòng lặp lồng nhau trên mảng tốn O(n²) vì chỉ số bên trong phải chạy lại từ đầu với mỗi vị trí của chỉ số bên ngoài. Nếu bạn chứng minh được rằng chỉ số bên trong không bao giờ cần lùi lại, thì tổng cộng hai chỉ số chỉ di chuyển nhiều nhất 2n bước, và thuật toán trở thành O(n).

Cả họ pattern này chỉ có vậy. Two pointers, fast-and-slow pointers, sliding window, cyclic sort, merge intervals — tất cả đều là “làm cho chỉ số thứ hai đơn điệu” khoác những bộ áo khác nhau. Và quan trọng là chúng đều chạy với bộ nhớ phụ O(1) (hoặc O(k) cho phần sổ sách của cửa sổ), đó chính là điểm phân biệt chúng với một mẹo O(n) phổ biến không kém: nhét hết mọi thứ vào hash table.

Cái bẫy nằm ở điều kiện tiên quyết. Gần như mọi thuật toán two-pointer đều dựa vào một tính chất cấu trúc nào đó của input để biện minh cho việc không bao giờ lùi lại: mảng đã sorted, các giá trị nằm trong khoảng đã biết 1..n, mọi số đều dương, hoặc ràng buộc của cửa sổ là đơn điệu (cửa sổ càng to thì ràng buộc chỉ càng khó thỏa mãn). Áp dụng pattern mà không kiểm tra điều kiện tiên quyết là cách phổ biến nhất khiến những lời giải này sai — two-sum bằng hai con trỏ đòi hỏi mảng đã sorted, và lời giải sliding window cho bài “subarray nhỏ nhất có tổng ≥ target” vỡ trận âm thầm ngay khi xuất hiện số âm.

Điều đó khiến họ pattern này trở thành người bạn đồng hành tự nhiên của sorting, vì cái giá O(n log n) của nó thường chính là thứ mua về tính sorted mà một lượt quét tuyến tính sau đó sẽ khai thác. Sort để dùng được two pointers là thuật toán O(n log n) tổng thể, nhưng thường vẫn thắng brute force O(n²) và thắng cả cách dùng hash table về mặt bộ nhớ.

Kiến thức nền tảng

Hai cấu hình con trỏ

Ngược chiều (hội tụ)                     Cùng chiều (cửa sổ / rượt đuổi)

  [ 1  3  5  7  9 11 ]                     [ a  b  c  d  e  f ]
    ^              ^                          ^     ^
    lo            hi                        left  right
    →              ←                          →     →

  lo và hi tiến về phía nhau;             cả hai đi sang phải; `right` mở rộng,
  vòng lặp kết thúc khi chúng gặp nhau.   `left` thu hẹp. Tổng bước ≤ 2n.

Ngược chiều đòi hỏi thứ tự: mảng phải sorted (hoặc bài toán đối xứng, như kiểm tra palindrome), vì quyết định “dịch lo hay dịch hi” được đưa ra bằng cách so với target và dựa vào thứ tự để biết bước nào mới có khả năng giúp ích.

Cùng chiều đòi hỏi tính đơn điệu của điều kiện: khi right tiến lên, đại lượng bạn đang theo dõi (một tổng, số ký tự phân biệt, một giá trị max) phải thay đổi theo chiều dự đoán được, để việc thu hẹp từ bên trái chắc chắn sửa được vi phạm.

Vì sao độ phức tạp lại ra như vậy

Lập luận ở đây là lập luận amortized, và đáng nói cho rõ một lần vì nó biện minh cho mọi thuật toán bên dưới. Trong vòng lặp sliding window:

left = 0
for right in range(n):
    add(a[right])
    while violates_constraint():
        remove(a[left])
        left += 1

Vòng while bên trong trông như thể làm cả thứ này thành bậc hai. Không phải: left chỉ tăng, và không bao giờ vượt quá right < n. Nên trên toàn bộ quá trình chạy của vòng ngoài, thân vòng trong được thực thi tối đa n lần tổng cộng — chứ không phải n lần mỗi vòng lặp. Tổng công việc là n lần tăng right cộng tối đa n lần tăng left, tức O(n). Đây cũng chính là lập luận amortized dùng cho việc dynamic array nở ra trong arrays: worst case tệ cho một bước riêng lẻ, rẻ khi tính trung bình, và cái trung bình mới là thứ chi phối tổng chi phí.

Ngay khi bạn viết code mà left có thể lùi lại, lập luận này sụp đổ và bạn quay về O(n²). Đó là phép thử để biết bạn có một lời giải two-pointer chính danh hay không.

Con trỏ ngược chiều

Two-sum trên mảng đã sorted. Ví dụ kinh điển. Brute force là O(n²); hash table cho O(n) thời gian với O(n) bộ nhớ và chạy được trên input chưa sorted; two pointers cho O(n) thời gian và O(1) bộ nhớ nhưng đòi hỏi mảng đã sorted.

def two_sum_sorted(nums, target):
    """Tìm chỉ số của hai giá trị có tổng bằng target trong mảng TĂNG DẦN.
    Bất biến: nếu tồn tại cặp hợp lệ thì cả hai chỉ số của nó nằm trong [lo, hi].
    Nếu nums[lo] + nums[hi] < target thì nums[lo] ghép với BẤT KỲ chỉ số nào trong
    [lo, hi] đều quá nhỏ (hi đã là lớn nhất còn lại), nên có thể loại bỏ lo.
    Chiều ngược lại đối xứng. Time O(n), space O(1)."""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        total = nums[lo] + nums[hi]
        if total == target:
            return (lo, hi)
        if total < target:
            lo += 1                # cần tổng lớn hơn
        else:
            hi -= 1                # cần tổng nhỏ hơn
    return None


assert two_sum_sorted([2, 7, 11, 15], 9) == (0, 1)
assert two_sum_sorted([1, 2, 3, 4, 6], 100) is None

Chú ý bất biến trong docstring — đó chính là kỷ luật loop invariant từ pseudocode và tính đúng đắn, và nó là thứ duy nhất biến “cứ loại lo đi” thành một nước đi có cơ sở thay vì một sự phỏng đoán.

Kiểm tra palindrome. Cùng khung xương, không cần sorted — tính đối xứng của bài toán thay thế cho điều đó.

def is_palindrome(s):
    """So sánh ký tự từ hai đầu vào giữa, bỏ qua ký tự không phải chữ/số và
    không phân biệt hoa thường. Time O(n), space O(1) — khác với s == s[::-1],
    vốn phải copy cả chuỗi."""
    lo, hi = 0, len(s) - 1
    while lo < hi:
        while lo < hi and not s[lo].isalnum():
            lo += 1
        while lo < hi and not s[hi].isalnum():
            hi -= 1
        if s[lo].lower() != s[hi].lower():
            return False
        lo, hi = lo + 1, hi - 1
    return True


assert is_palindrome("A man, a plan, a canal: Panama")
assert not is_palindrome("race a car")

Container with most water. Bài học được nhiều nhất trong ba bài, vì lý do để dịch con trỏ là một chứng minh thực thụ chứ không phải một phép so sánh hiển nhiên.

def max_area(heights):
    """Hai đường thẳng đứng cùng trục hoành tạo thành một bể chứa; tối đa hóa
    lượng nước. Diện tích = (hi - lo) * min(heights[lo], heights[hi]).
    Dịch đường THẤP HƠN vào trong. Vì sao an toàn: đường thấp hơn khống chế
    diện tích của mọi cặp mà nó tham gia, và mọi bạn đồng hành khác của nó đều
    có chiều rộng nhỏ hơn hẳn — nên không cặp nào chứa đường thấp hơn có thể
    thắng được cái ta vừa đo. Loại nó đi không mất gì cả.
    Time O(n), space O(1)."""
    lo, hi = 0, len(heights) - 1
    best = 0
    while lo < hi:
        best = max(best, (hi - lo) * min(heights[lo], heights[hi]))
        if heights[lo] < heights[hi]:
            lo += 1
        else:
            hi -= 1
    return best


assert max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49

Nếu bạn không diễn đạt được vì sao dịch đường thấp hơn là an toàn thì bạn đang thuộc lòng lời giải chứ không hiểu nó — và biến thể tiếp theo của bài toán sẽ hạ gục bạn. Đây chính xác là kiểu lập luận trao đổi (exchange argument) dùng để biện minh cho thuật toán greedy.

Khái niệm chính

Fast and slow pointers (rùa và thỏ của Floyd)

Khi cấu trúc là linked list chứ không phải mảng, bạn không thể truy cập theo index, nên “phần tử giữa” và “phần tử thứ n từ cuối” không địa chỉ hóa trực tiếp được. Hai con trỏ chạy với tốc độ khác nhau giải quyết được cả hai — và cùng ý tưởng đó phát hiện được cycle.

   1 → 2 → 3 → 4 → 5
           ↑         ↓
           8 ← 7 ← 6
   |--μ--|----- λ -----|
   μ = khoảng cách tới điểm vào cycle, λ = độ dài cycle

Phát hiện cycle. Cho slow đi một node mỗi bước và fast đi hai. Nếu không có cycle, fast chạy hết list. Nếu có cycle, fast vào cycle trước, slow vào sau, và từ đó fast rút ngắn đúng một vị trí so với slow sau mỗi bước.

Phác thảo chứng minh chúng buộc phải gặp nhau. Khi cả hai con trỏ đã ở trong cycle, xét khoảng cách d = (vị trí của fast − vị trí của slow) đo xuôi vòng quanh cycle, lấy modulo λ. Mỗi bước, fast tiến 2 và slow tiến 1, nên d tăng đúng 1 mỗi bước, modulo λ. Vì d nhận giá trị trong {0, 1, …, λ−1} và tăng 1 mỗi bước, nó sẽ đạt 0 trong tối đa λ bước — và d = 0 nghĩa là hai con trỏ đang ở cùng một node. Chúng không thể “nhảy vượt qua” nhau, vì khoảng cách chỉ đổi đúng một node mỗi bước. Tổng thời gian là O(μ + λ) = O(n).

Tìm điểm vào cycle. Giả sử điểm gặp nhau nằm cách điểm vào k node bên trong cycle. slow đã đi μ + k; fast đã đi 2(μ + k), đồng thời cũng bằng μ + k + mλ với số nguyên m ≥ 1 nào đó (nó chạy thêm m vòng). Cân bằng lại: 2(μ + k) = μ + k + mλ, suy ra μ + k = mλ, tức μ = mλ − k. Điều đó nói rằng: xuất phát từ head và đi μ bước sẽ tới đúng điểm vào cycle; xuất phát từ điểm gặp nhau và đi μ bước cũng tới đúng điểm vào cycle (vì μ + k ≡ 0 mod λ). Vậy hãy đưa một con trỏ về head, cho cả hai tiến từng bước một, và chúng sẽ gặp nhau đúng tại điểm vào.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next


def has_cycle(head):
    """Phát hiện cycle kiểu Floyd. Time O(n), space O(1) — bộ nhớ O(1) chính là
    điểm mấu chốt; dùng một set `visited` sẽ tốn O(n) bộ nhớ."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False


def cycle_start(head):
    """Trả về node đầu tiên của cycle, hoặc None. Pha 1 tìm điểm gặp nhau;
    pha 2 dùng mu = m*lambda - k để đi tới điểm vào.
    Time O(n), space O(1)."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            finder = head
            while finder is not slow:      # cả hai cùng tiến một bước mỗi lần
                finder, slow = finder.next, slow.next
            return finder
    return None


def middle_node(head):
    """Khi fast chạm cuối list sau khi đã đi gấp đôi quãng đường, slow đang ở giữa.
    Với list độ dài chẵn, hàm này trả về node giữa THỨ HAI; muốn node giữa thứ nhất
    thì cho fast xuất phát từ head.next. Time O(n), space O(1)."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
    return slow


def remove_nth_from_end(head, n):
    """Cho `lead` chạy trước n node, rồi cho cả hai cùng tiến tới khi `lead` chạm
    cuối; khi đó `trail` đứng ngay trước node cần xóa. Node dummy loại bỏ trường
    hợp đặc biệt khi phải xóa chính head.
    Time O(n) chỉ trong MỘT lượt duyệt, space O(1)."""
    dummy = Node(None, head)
    lead = trail = dummy
    for _ in range(n):
        lead = lead.next
    while lead.next is not None:
        lead, trail = lead.next, trail.next
    trail.next = trail.next.next
    return dummy.next


def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head


def to_list(head):
    out = []
    while head is not None:
        out.append(head.value)
        head = head.next
    return out


lst = build([1, 2, 3, 4, 5])
assert middle_node(lst).value == 3
assert to_list(remove_nth_from_end(build([1, 2, 3, 4, 5]), 2)) == [1, 2, 3, 5]
assert not has_cycle(build([1, 2, 3]))

cyc = build([1, 2, 3, 4])
cyc.next.next.next.next = cyc.next          # 4 trỏ ngược về 2
assert has_cycle(cyc)
assert cycle_start(cyc).value == 2

Fast and slow pointers cũng là cách phát hiện cycle trong một functional graph — dãy x, f(x), f(f(x)), … trong đó mỗi phần tử có đúng một phần tử kế tiếp. Điều đó bao gồm bài “tìm số bị lặp trong mảng n+1 số nguyên thuộc khoảng 1..n” (coi i → nums[i] là hàm kế tiếp; một số lặp bắt buộc tạo ra cycle) và thuật toán phân tích thừa số Pollard’s rho. Xem linked lists để biết thêm về thao tác con trỏ trên list.

Cửa sổ trượt kích thước cố định

Khi kích thước cửa sổ đã cho trước, cửa sổ chính là một queue: thêm bên phải, bỏ bên trái, và không bao giờ tính lại đại lượng tổng hợp từ đầu.

def max_sum_subarray_k(nums, k):
    """Tổng lớn nhất của một subarray liên tiếp có đúng độ dài k.
    Bản ngây thơ tính lại tổng mỗi cửa sổ mất O(k), cho tổng cộng O(n*k).
    Ở đây mỗi lần trượt chỉ tốn O(1): cộng phần tử vào, trừ phần tử ra.
    Time O(n), space O(1)."""
    if len(nums) < k:
        return None
    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]
        best = max(best, window)
    return best


assert max_sum_subarray_k([2, 1, 5, 1, 3, 2], 3) == 9      # [5, 1, 3]

Cùng cấu trúc “thêm một, bỏ một” đó xử lý được trung bình trên cửa sổ cố định, tìm anagram (giữ một dictionary đếm ký tự thay vì một tổng), và rolling hash để tìm chuỗi con (Rabin–Karp). Khi đại lượng tổng hợp là giá trị lớn nhất thay vì tổng, bạn không thể trừ phần tử rời cửa sổ đi, và cần tới monotonic deque — xem stack và queue.

Cửa sổ trượt kích thước thay đổi

Cửa sổ nở ra cho tới khi một ràng buộc bị phá vỡ, rồi co lại cho tới khi ràng buộc được thỏa mãn trở lại. Đây chính là khung for right / while left trong phần lập luận độ phức tạp ở trên.

Chuỗi con dài nhất không có ký tự lặp — nở ra, và co lại mỗi khi có ký tự trùng lọt vào.

def longest_unique_substring(s):
    """Nở cửa sổ bằng cách dịch `right`; nếu s[right] đã nằm bên trong thì dịch
    `left` vượt qua lần xuất hiện trước đó. Lưu CHỈ SỐ CUỐI CÙNG của mỗi ký tự
    cho phép left nhảy thẳng thay vì bò từng bước — cả hai đều là O(n) tổng thể,
    nhưng bản nhảy dễ lập luận hơn.
    Time O(n), space O(min(n, alphabet))."""
    last_seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1       # không bao giờ để left lùi lại
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best


assert longest_unique_substring("abcabcbb") == 3     # "abc"
assert longest_unique_substring("bbbbb") == 1
assert longest_unique_substring("pwwkew") == 3       # "wke"

Điều kiện last_seen[ch] >= left là chỗ tinh vi: nếu thiếu nó, một ký tự đã gặp từ rất lâu (hiện đã nằm ngoài cửa sổ) sẽ kéo left lùi lại, phá vỡ cả tính đúng đắn lẫn cận O(n).

Minimum window substring — bài khó nhất trong các bài cửa sổ tiêu chuẩn, và đáng nghiên cứu vì nó cho thấy template tổng quát với một phép kiểm tra “ràng buộc đã thỏa mãn chưa” không hề tầm thường.

def min_window(s, t):
    """Chuỗi con nhỏ nhất của s chứa mọi ký tự của t kể cả số lần lặp.
    `need` đếm những gì còn thiếu (có thể âm = dư).
    `missing` đếm còn nợ bao nhiêu ký tự, nhờ vậy phép kiểm tra thỏa mãn chỉ tốn
    O(1) thay vì so sánh hai dictionary ở mỗi bước.
    Time O(len(s) + len(t)), space O(alphabet)."""
    if not t or not s:
        return ""
    need = {}
    for ch in t:
        need[ch] = need.get(ch, 0) + 1
    missing = len(t)

    best_len = len(s) + 1
    best_start = 0
    left = 0
    for right, ch in enumerate(s):
        if need.get(ch, 0) > 0:
            missing -= 1                    # ký tự này vẫn đang còn nợ
        need[ch] = need.get(ch, 0) - 1

        while missing == 0:                 # cửa sổ hợp lệ — thử co lại
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_start = left
            need[s[left]] += 1
            if need[s[left]] > 0:           # bỏ nó đi thì cửa sổ hết hợp lệ
                missing += 1
            left += 1
    return "" if best_len > len(s) else s[best_start:best_start + best_len]


assert min_window("ADOBECODEBANC", "ABC") == "BANC"
assert min_window("a", "aa") == ""

Template tổng quát, đáng học thuộc như một hình dạng chứ không phải như code:

left = 0
for right in range(n):
    include a[right] in the window state
    while window is invalid (or: while window is valid, for a "minimum" problem):
        update the answer if appropriate
        remove a[left] from the window state
        left += 1
    update the answer if appropriate

Việc cập nhật đáp án nằm trong hay ngoài vòng while chính là khác biệt giữa “cửa sổ hợp lệ dài nhất” (cập nhật ở ngoài, sau khi đã khôi phục tính hợp lệ) và “cửa sổ hợp lệ ngắn nhất” (cập nhật ở trong, khi cửa sổ còn hợp lệ). Làm ngược lại là lỗi tiêu chuẩn.

Điều kiện tiên quyết mà ai cũng quên: bước co lại phải chắc chắn giúp ích. Với bài “subarray nhỏ nhất có tổng ≥ target”, điều đó đòi hỏi mọi số đều không âm — nếu có số âm, bỏ một phần tử đi có thể làm tăng tổng, ràng buộc không còn đơn điệu theo cửa sổ nữa, và thuật toán trả về kết quả vô nghĩa. Biến thể đó cần prefix sum cộng monotonic deque, hoặc một cách tiếp cận hoàn toàn khác.

Cyclic sort

Khi mảng là một hoán vị của 1..n (hoặc 0..n−1), mỗi giá trị có chỉ số nhà đã biết. Điều đó biến việc sắp xếp thành một số lượng tuyến tính phép swap mà không cần so sánh nào — và hữu ích hơn nữa, biến bài “tìm số thiếu / số lặp” thành một lượt quét hai dòng sau đó.

def cyclic_sort(nums):
    """Đưa mọi giá trị v về chỉ số v-1, với O(n) thời gian và O(1) bộ nhớ.
    Điều kiện tiên quyết: nums là hoán vị của 1..n.
    Vòng lặp là O(n), không phải O(n^2): mỗi lần swap đưa ít nhất một giá trị về
    đúng nhà, và giá trị đã về nhà thì không bao giờ bị dịch nữa — nên tổng cộng
    có nhiều nhất n lần swap trên toàn bộ quá trình chạy."""
    i = 0
    while i < len(nums):
        home = nums[i] - 1
        if nums[i] != nums[home]:           # so sánh GIÁ TRỊ, không phải chỉ số —
            nums[i], nums[home] = nums[home], nums[i]   # nhờ vậy xử lý an toàn khi có số lặp
        else:
            i += 1
    return nums


def find_missing_and_duplicate(nums):
    """Dành cho mảng 1..n có đúng một giá trị bị lặp và một giá trị bị thiếu.
    Cyclic sort xong, chỉ số duy nhất có nums[i] != i+1 lộ ra cả hai giá trị.
    Time O(n), space O(1)."""
    cyclic_sort(nums)
    for i, v in enumerate(nums):
        if v != i + 1:
            return (i + 1, v)               # (số thiếu, số lặp)
    return None


assert cyclic_sort([3, 1, 5, 4, 2]) == [1, 2, 3, 4, 5]
assert find_missing_and_duplicate([3, 1, 2, 5, 2]) == (4, 2)

Việc so sánh nums[i] != nums[home] thay vì nums[i] != home + 1 không phải chuyện phong cách: khi có số lặp, phép kiểm tra dựa trên chỉ số sẽ lặp vô hạn, cứ swap qua lại hai giá trị bằng nhau. Đây là loại chi tiết chỉ lộ ra khi bạn test edge case.

Cyclic sort là trường hợp đặc biệt của quan sát rằng khoảng giá trị đã biết cũng là một dạng của tính sorted — cùng insight đứng sau counting sort và radix sort trong thuật toán sắp xếp. Nó chỉ đạt được O(1) bộ nhớ vì các giá trị chính là các chỉ số; ở đây không có phép màu “sắp xếp tuyến tính” tổng quát nào cả.

Merge intervals

Các bài về interval trở thành pattern two-pointer ngay khi bạn sort theo thời điểm bắt đầu: một lượt quét từ trái sang phải, duy trì “interval đang được dựng”.

def merge_intervals(intervals):
    """Gộp mọi interval chồng lấn.
    Sort theo start; khi đó mọi interval bắt đầu tại hoặc trước điểm kết thúc của
    interval hiện tại đều phải chồng lấn với nó, vì mọi thứ phía sau còn muộn hơn.
    Time O(n log n) — chi phối bởi phép sort; bản thân lượt quét gộp chỉ là O(n).
    Space O(n) cho output (O(1) bộ nhớ phụ nếu gộp tại chỗ)."""
    if not intervals:
        return []
    ordered = sorted(intervals, key=lambda iv: iv[0])
    merged = [list(ordered[0])]
    for start, end in ordered[1:]:
        if start <= merged[-1][1]:          # chồng lấn (dùng < nếu chạm nhau không tính là chồng)
            merged[-1][1] = max(merged[-1][1], end)   # max: interval hiện tại có thể BAO TRỌN cái sau
        else:
            merged.append([start, end])
    return [tuple(iv) for iv in merged]


def interval_intersection(a, b):
    """Giao hai danh sách interval rời nhau, đã sorted, bằng hai con trỏ.
    Giao của [s1,e1] và [s2,e2] là [max(s1,s2), min(e1,e2)], khác rỗng khi và chỉ
    khi cận dưới đó <= cận trên đó. Tiến con trỏ của interval kết thúc sớm hơn —
    nó không thể giao với bất cứ thứ gì phía sau nữa.
    Time O(n + m), space O(output)."""
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        lo = max(a[i][0], b[j][0])
        hi = min(a[i][1], b[j][1])
        if lo <= hi:
            out.append((lo, hi))
        if a[i][1] < b[j][1]:
            i += 1
        else:
            j += 1
    return out


assert merge_intervals([(1, 3), (2, 6), (8, 10), (15, 18)]) == [(1, 6), (8, 10), (15, 18)]
assert merge_intervals([(1, 10), (2, 3)]) == [(1, 10)]
assert interval_intersection([(0, 2), (5, 10)], [(1, 5), (8, 12)]) == [(1, 2), (5, 5), (8, 10)]

max(merged[-1][1], end) là chỗ mà phần lớn bản hiện thực làm sai. Nếu interval đang gộp là (1, 10) và cái tiếp theo là (2, 3), gán thẳng end sẽ co nó lại thành (1, 3) và mất dữ liệu. Sort theo start không kéo theo sort theo end.

Một pattern liên quan đáng biết: với bài “số interval chồng lấn nhiều nhất” (meeting rooms, đỉnh đồng thời), đừng gộp — hãy tách mỗi interval thành một sự kiện +1 ở điểm bắt đầu và −1 ở điểm kết thúc, sort cả 2n sự kiện, rồi quét trong khi giữ một bộ đếm chạy. Đó là sweep line, công cụ tổng quát mà merge intervals chỉ là một trường hợp riêng.

Prefix sums — người anh em tiền xử lý

Prefix sum không phải kỹ thuật con trỏ, nhưng nó thuộc về bài này vì nó giải cùng một lớp bài toán — tổng hợp trên một đoạn liên tiếp — và nó phủ đúng những trường hợp mà sliding window thất bại (có số âm, đoạn tùy ý thay vì cửa sổ).

def build_prefix(nums):
    """prefix[i] = tổng của i phần tử đầu tiên, prefix[0] = 0.
    Số 0 dẫn đầu chính là thứ khiến range_sum không cần trường hợp đặc biệt.
    Dựng mất O(n), sau đó mọi truy vấn đoạn chỉ tốn O(1). Space O(n)."""
    prefix = [0] * (len(nums) + 1)
    for i, v in enumerate(nums):
        prefix[i + 1] = prefix[i] + v
    return prefix


def range_sum(prefix, lo, hi):
    """Tổng của nums[lo:hi+1], bao gồm cả hai đầu. O(1)."""
    return prefix[hi + 1] - prefix[lo]


def subarray_sum_equals_k(nums, k):
    """Đếm số subarray liên tiếp có tổng đúng bằng k — CHẠY ĐƯỢC với số âm,
    nơi sliding window bó tay.
    sum(i..j) == k  <=>  prefix[j+1] - prefix[i] == k  <=>  prefix[i] == prefix[j+1] - k
    nên tại mỗi j, hãy đếm xem có bao nhiêu prefix trước đó mang giá trị cần thiết.
    Time O(n), space O(n) cho bảng đếm."""
    counts = {0: 1}                    # prefix rỗng, để subarray bắt đầu từ 0 được tính
    running = 0
    total = 0
    for v in nums:
        running += v
        total += counts.get(running - k, 0)
        counts[running] = counts.get(running, 0) + 1
    return total


p = build_prefix([1, 2, 3, 4, 5])
assert range_sum(p, 1, 3) == 9         # 2 + 3 + 4
assert subarray_sum_equals_k([1, 1, 1], 2) == 2
assert subarray_sum_equals_k([1, -1, 0], 0) == 3

itertools.accumulate(nums, initial=0) cho bạn mảng prefix trong một lời gọi chạy ở tốc độ C và đó là thứ bạn thực sự sẽ viết. Các mở rộng đáng biết: prefix sum 2D (bao hàm–loại trừ trên một hình chữ nhật, O(1) mỗi truy vấn sau khi dựng O(rc)), difference array (phép nghịch đảo — cập nhật đoạn O(1), một lượt duyệt để hiện thực hóa), và khi mảng nền thay đổi giữa các truy vấn thì dùng Fenwick tree hoặc segment tree cho O(log n) mỗi lần cập nhật và truy vấn.

Biến thể multi-threaded

Roadmap liệt kê một node “multi-threaded” bên cạnh các pattern này, và mối liên hệ là có thật: nhiều bài trong số này có dạng phát biểu song song, trong đó “con trỏ” là các worker độc lập chứ không phải chỉ số trong một vòng lặp. Chia mảng thành k khối, cho k thread mỗi thread tính một kết quả bộ phận, rồi gộp lại — một merge sort mà hai nửa được sort song song, một prefix sum tính bằng parallel scan, một phép tìm kiếm mà nhiều worker cùng quét các lát rời nhau.

Ba điều đáng biết trước khi dùng tới nó:

• Chỉ những phép tổng hợp có tính kết hợp mới song song hóa sạch sẽ. Sum, max, min và count đều có tính kết hợp, nên kết quả bộ phận gộp lại theo thứ tự nào cũng được. “Chuỗi con dài nhất không có ký tự lặp” thì không phân rã kiểu đó được — một cửa sổ có thể nằm vắt qua ranh giới hai khối, và việc khâu các ranh giới lại thường khó hơn cả thuật toán tuần tự.
• Các thuật toán tuần tự ở đây vốn đã là O(n) và bị chặn bởi bộ nhớ, không phải bởi tính toán. Song song hóa một lượt quét tuyến tính thường lời ít hơn nhiều so với con số thread gợi ý, vì giới hạn nằm ở memory bandwidth chứ không ở CPU.
• Riêng với CPython, GIL khiến thread không hề tăng tốc phần việc CPU thuần Python. Hãy dùng multiprocessing, một C extension có nhả GIL (NumPy), hoặc bản build free-threaded. Đây là ràng buộc thật chứ không phải chú thích cho vui: một phép tính tổng “song song” ngây thơ dựa trên threading trong Python luôn chậm hơn vòng lặp đơn luồng.

Concurrency thuộc về một phần khác của chương trình học so với các pattern thuật toán ở đây; điều rút ra hữu ích là cách phân rã mới là thứ khiến một thuật toán song song hóa được, và các pattern two-pointer về bản chất phần lớn là tuần tự vì mỗi bước phụ thuộc vào bước trước.

Chọn pattern nào

Bài toán ngửi mùi giống…	Hãy dùng…	Độ phức tạp điển hình
”Tìm cặp có tổng bằng X” trong mảng đã sorted	Two pointers ngược chiều	O(n) thời gian, O(1) bộ nhớ
”Tìm cặp có tổng bằng X”, chưa sorted, thứ tự không quan trọng	Hash set, hoặc sort trước rồi two pointers	O(n) / O(n log n)
”Bộ ba có tổng bằng X” (3-sum)	Sort, cố định một phần tử, two pointers phần còn lại	O(n²)
Kiểm tra palindrome / đối xứng gương	Two pointers ngược chiều	O(n) thời gian, O(1) bộ nhớ
”Tối đa hóa thứ gì đó giữa hai đầu” (container, hứng nước mưa)	Ngược chiều, dịch bên đang bị giới hạn	O(n)
”Subarray liên tiếp có kích thước đúng bằng k”	Cửa sổ trượt kích thước cố định	O(n)
”Subarray/chuỗi con dài nhất/ngắn nhất thỏa mãn …”	Cửa sổ trượt kích thước thay đổi	O(n)
Vẫn vậy nhưng mảng chứa số âm	Prefix sum + hash map (cửa sổ vỡ trận)	O(n)
”Tổng trên một đoạn tùy ý”, mảng không đổi	Prefix sums	O(n) dựng, O(1) truy vấn
Vẫn vậy nhưng mảng bị cập nhật giữa các truy vấn	Fenwick / segment tree	O(log n) mỗi thao tác
Linked list: cycle, phần tử giữa, phần tử thứ n từ cuối	Fast and slow pointers	O(n) thời gian, O(1) bộ nhớ
Giá trị là hoán vị của 1..n; tìm số thiếu/số lặp	Cyclic sort	O(n) thời gian, O(1) bộ nhớ
Các đoạn chồng lấn: “gộp”/“chèn”/“có xung đột không”	Sort theo start rồi gộp tuyến tính	O(n log n)
”Lúc đông nhất có bao nhiêu cái chồng lên nhau”	Sweep line (sự kiện +1/−1)	O(n log n)
Hai danh sách đã sorted cần gộp hoặc giao	Two pointers, mỗi list một con trỏ	O(n + m)
Gộp k danh sách đã sorted	Heap trên k phần tử đầu	O(N log k)

Bảng tổng kết độ phức tạp

Thuật toán	Time	Bộ nhớ phụ	Điều kiện tiên quyết
Two-sum (đã sorted)	O(n)	O(1)	Mảng đã sorted
Kiểm tra palindrome	O(n)	O(1)	—
Container with most water	O(n)	O(1)	—
Phát hiện cycle kiểu Floyd	O(μ + λ) = O(n)	O(1)	Mỗi node có ≤ 1 successor
Node giữa / thứ n từ cuối	O(n)	O(1)	—
Cửa sổ kích thước cố định	O(n)	O(1) hoặc O(k)	Đại lượng tổng hợp phải khả nghịch
Cửa sổ kích thước thay đổi	O(n) amortized	O(alphabet)	Ràng buộc đơn điệu theo kích thước cửa sổ
Minimum window substring	O(n + m)	O(alphabet)	—
Cyclic sort	O(n)	O(1)	Giá trị là hoán vị của 1..n
Merge intervals	O(n log n)	O(n)	— (sort chi phối)
Prefix sum dựng / truy vấn	O(n) / O(1)	O(n)	Mảng không đổi giữa các truy vấn
Subarray sum equals k	O(n)	O(n)	— (chạy được với số âm)

Best Practices

• Nêu điều kiện tiên quyết trước khi viết vòng lặp. Đã sorted chưa? Có không âm không? Giá trị có thuộc 1..n không? Mọi thuật toán ở đây đều sai nếu thiếu điều kiện của nó, và sai một cách âm thầm — nó trả về một con số nghe có lý, chứ không ném exception.
• Viết bất biến ra thành comment. “Nếu tồn tại cặp hợp lệ thì cả hai chỉ số của nó nằm trong [lo, hi]” chính là thứ khiến việc loại bỏ một vị trí con trỏ trở nên có cơ sở. Nếu bạn không viết được bất biến, bạn đang khớp mẫu chứ không giải bài.
• Kiểm tra rằng không con trỏ nào từng lùi lại. Riêng tính chất đó là thứ làm thuật toán tuyến tính. Nếu left của bạn có thể giảm, phân tích độ phức tạp của bạn sai.
• Đặt vị trí cập nhật đáp án một cách có chủ đích. “Cửa sổ hợp lệ dài nhất” cập nhật đáp án sau khi vòng co lại đã khôi phục tính hợp lệ; “cửa sổ hợp lệ ngắn nhất” cập nhật bên trong vòng lặp khi cửa sổ còn hợp lệ. Đây là lỗi sliding window phổ biến nhất.
• Đừng bao giờ dùng sliding window khi có thể có giá trị âm trong bài ràng buộc theo tổng. Nở cửa sổ không còn làm tổng tăng đơn điệu nữa, nên co lại không chắc giúp ích. Hãy dùng prefix sum cộng hash map.
• Dùng node dummy/sentinel khi phẫu thuật con trỏ trên linked list. Nó loại bỏ trường hợp đặc biệt “nếu phải xóa chính head thì sao”, vốn là nơi bug tụ tập — xem linked lists.
• Test biên một cách tường minh: input rỗng, một phần tử, hai phần tử, mọi phần tử giống hệt nhau, target nằm ở vị trí đầu tiên hoặc cuối cùng, kích thước cửa sổ lớn hơn cả mảng. Các pattern này dày đặc lỗi off-by-one và mỗi input đó phá vỡ một bản hiện thực ngây thơ khác nhau.
• Ưu tiên standard library ở những chỗ nó đã có sẵn. itertools.accumulate cho prefix sum, collections.deque cho monotonic window, sorted cho phép sort interval, bisect cho binary search. Bản tự viết chạy chậm hơn trong CPython (chúng là vòng lặp Python chứ không phải vòng lặp C) và nhiều bug hơn.
• Sort để dùng được two pointers thường là đáng. O(n log n) cộng một lượt quét O(n) thắng brute force O(n²) với mọi n đáng bận tâm, và dùng O(1) bộ nhớ phụ ở nơi lời giải hash table tốn O(n). Ngoại lệ là khi chỉ số gốc có ý nghĩa và bạn không kham nổi việc ghi lại chúng.
• Đừng dùng thread để tăng tốc một lượt quét tuyến tính. Các thuật toán này bị chặn bởi memory bandwidth và phần lớn vốn dĩ tuần tự; dưới GIL của CPython, “song song” bằng thread cho phần việc CPU thuần Python còn chậm hơn vòng lặp thường.
• Khi cửa sổ không dùng được, phương án dự phòng gần như luôn là prefix sum, monotonic deque, hoặc heap. Biết danh sách ngắn đó giúp bạn khỏi ngồi nhìn chằm chằm một lời giải cửa sổ đã hỏng để cố vá nó.

Tài liệu tham khảo

• roadmap.sh — Data Structures & Algorithms
• Two-pointer technique — Wikipedia
• Cycle detection (Floyd’s tortoise and hare) — Wikipedia
• Sliding window protocol / technique — Wikipedia
• cp-algorithms — Prefix sums and difference arrays (Sparse Table article covers range queries)
• cp-algorithms — Fenwick Tree
• Sweep line algorithm — Wikipedia
• Rabin–Karp algorithm — Wikipedia
• CLRS — Introduction to Algorithms, Chapter 17: Amortized Analysis
• Python Documentation — itertools.accumulate
• Python Documentation — collections.deque
• Python Documentation — Global Interpreter Lock

Opposite direction (converging)          Same direction (window / chasing)

  [ 1  3  5  7  9 11 ]                     [ a  b  c  d  e  f ]
    ^              ^                          ^     ^
    lo            hi                        left  right
    →              ←                          →     →

  lo and hi walk toward each other;       both walk right; `right` expands,
  the loop ends when they meet.           `left` contracts. Total moves ≤ 2n.

left = 0
for right in range(n):
    add(a[right])
    while violates_constraint():
        remove(a[left])
        left += 1

def two_sum_sorted(nums, target):
    """Find indices of two values summing to target in an ASCENDING array.
    Invariant: if a valid pair exists, both its indices lie in [lo, hi].
    If nums[lo] + nums[hi] < target, then nums[lo] paired with ANY index in
    [lo, hi] is too small (hi is the largest available), so lo can be discarded.
    Symmetrically for the other direction. Time O(n), space O(1)."""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        total = nums[lo] + nums[hi]
        if total == target:
            return (lo, hi)
        if total < target:
            lo += 1                # need a bigger sum
        else:
            hi -= 1                # need a smaller sum
    return None


assert two_sum_sorted([2, 7, 11, 15], 9) == (0, 1)
assert two_sum_sorted([1, 2, 3, 4, 6], 100) is None

def is_palindrome(s):
    """Compare characters from both ends inward, ignoring non-alphanumerics
    and case. Time O(n), space O(1) — unlike s == s[::-1], which copies."""
    lo, hi = 0, len(s) - 1
    while lo < hi:
        while lo < hi and not s[lo].isalnum():
            lo += 1
        while lo < hi and not s[hi].isalnum():
            hi -= 1
        if s[lo].lower() != s[hi].lower():
            return False
        lo, hi = lo + 1, hi - 1
    return True


assert is_palindrome("A man, a plan, a canal: Panama")
assert not is_palindrome("race a car")

def max_area(heights):
    """Two vertical lines and the x-axis form a container; maximize the water.
    Area = (hi - lo) * min(heights[lo], heights[hi]).
    Move the SHORTER line inward. Why it is safe: the shorter line caps the
    area for every pair it takes part in, and any other partner for it would
    have a strictly smaller width — so no pair involving the shorter line can
    beat what we just measured. Discarding it loses nothing.
    Time O(n), space O(1)."""
    lo, hi = 0, len(heights) - 1
    best = 0
    while lo < hi:
        best = max(best, (hi - lo) * min(heights[lo], heights[hi]))
        if heights[lo] < heights[hi]:
            lo += 1
        else:
            hi -= 1
    return best


assert max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49

   1 → 2 → 3 → 4 → 5
           ↑         ↓
           8 ← 7 ← 6
   |--μ--|----- λ -----|
   μ = distance to cycle entry, λ = cycle length

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next


def has_cycle(head):
    """Floyd's cycle detection. Time O(n), space O(1) — the O(1) space is the
    whole point; a `visited` set would be O(n) memory."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False


def cycle_start(head):
    """Return the first node of the cycle, or None. Phase 1 finds a meeting
    point; phase 2 uses mu = m*lambda - k to walk to the entry.
    Time O(n), space O(1)."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            finder = head
            while finder is not slow:      # both advance one step at a time
                finder, slow = finder.next, slow.next
            return finder
    return None


def middle_node(head):
    """When fast reaches the end having moved twice as far, slow is halfway.
    For an even-length list this returns the SECOND middle node; start fast
    at head.next instead to get the first. Time O(n), space O(1)."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
    return slow


def remove_nth_from_end(head, n):
    """Give `lead` an n-node head start, then advance both until `lead` falls
    off the end; `trail` is then just before the node to remove. The dummy
    node removes the special case of deleting the head itself.
    Time O(n) in ONE pass, space O(1)."""
    dummy = Node(None, head)
    lead = trail = dummy
    for _ in range(n):
        lead = lead.next
    while lead.next is not None:
        lead, trail = lead.next, trail.next
    trail.next = trail.next.next
    return dummy.next


def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head


def to_list(head):
    out = []
    while head is not None:
        out.append(head.value)
        head = head.next
    return out


lst = build([1, 2, 3, 4, 5])
assert middle_node(lst).value == 3
assert to_list(remove_nth_from_end(build([1, 2, 3, 4, 5]), 2)) == [1, 2, 3, 5]
assert not has_cycle(build([1, 2, 3]))

cyc = build([1, 2, 3, 4])
cyc.next.next.next.next = cyc.next          # 4 points back to 2
assert has_cycle(cyc)
assert cycle_start(cyc).value == 2

def max_sum_subarray_k(nums, k):
    """Maximum sum of any contiguous subarray of exactly length k.
    The naive version recomputes each window's sum in O(k), giving O(n*k).
    Here each slide is O(1): add the entering element, subtract the leaving one.
    Time O(n), space O(1)."""
    if len(nums) < k:
        return None
    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]
        best = max(best, window)
    return best


assert max_sum_subarray_k([2, 1, 5, 1, 3, 2], 3) == 9      # [5, 1, 3]

def longest_unique_substring(s):
    """Grow the window by moving `right`; if s[right] is already inside,
    move `left` past its previous occurrence. Storing the LAST INDEX of each
    character lets left jump directly instead of stepping one at a time —
    both are O(n) overall, but the jump version is simpler to reason about.
    Time O(n), space O(min(n, alphabet))."""
    last_seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1       # never move left backwards
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best


assert longest_unique_substring("abcabcbb") == 3     # "abc"
assert longest_unique_substring("bbbbb") == 1
assert longest_unique_substring("pwwkew") == 3       # "wke"

def min_window(s, t):
    """Smallest substring of s containing every character of t with multiplicity.
    `need` counts what is still missing (can go negative = surplus).
    `missing` counts how many characters are still owed, so the satisfaction
    check is O(1) instead of comparing two dictionaries every step.
    Time O(len(s) + len(t)), space O(alphabet)."""
    if not t or not s:
        return ""
    need = {}
    for ch in t:
        need[ch] = need.get(ch, 0) + 1
    missing = len(t)

    best_len = len(s) + 1
    best_start = 0
    left = 0
    for right, ch in enumerate(s):
        if need.get(ch, 0) > 0:
            missing -= 1                    # this character was still owed
        need[ch] = need.get(ch, 0) - 1

        while missing == 0:                 # window is valid — try to shrink it
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_start = left
            need[s[left]] += 1
            if need[s[left]] > 0:           # dropping it breaks validity
                missing += 1
            left += 1
    return "" if best_len > len(s) else s[best_start:best_start + best_len]


assert min_window("ADOBECODEBANC", "ABC") == "BANC"
assert min_window("a", "aa") == ""

left = 0
for right in range(n):
    include a[right] in the window state
    while window is invalid (or: while window is valid, for a "minimum" problem):
        update the answer if appropriate
        remove a[left] from the window state
        left += 1
    update the answer if appropriate

def cyclic_sort(nums):
    """Place every value v at index v-1, in O(n) time and O(1) space.
    Precondition: nums is a permutation of 1..n.
    The loop is O(n), not O(n^2): each swap puts at least one value into its
    final home, and a value in its home is never moved again — so there are
    at most n swaps in total across the whole run."""
    i = 0
    while i < len(nums):
        home = nums[i] - 1
        if nums[i] != nums[home]:           # compare VALUES, not indices —
            nums[i], nums[home] = nums[home], nums[i]   # handles duplicates safely
        else:
            i += 1
    return nums


def find_missing_and_duplicate(nums):
    """For an array of 1..n with exactly one value duplicated and one missing.
    Sort cyclically, then the single index where nums[i] != i+1 reveals both.
    Time O(n), space O(1)."""
    cyclic_sort(nums)
    for i, v in enumerate(nums):
        if v != i + 1:
            return (i + 1, v)               # (missing, duplicate)
    return None


assert cyclic_sort([3, 1, 5, 4, 2]) == [1, 2, 3, 4, 5]
assert find_missing_and_duplicate([3, 1, 2, 5, 2]) == (4, 2)

def merge_intervals(intervals):
    """Merge all overlapping intervals.
    Sort by start; then any interval that begins at or before the current
    interval's end must overlap it, because everything after is even later.
    Time O(n log n) — dominated by the sort; the merge scan itself is O(n).
    Space O(n) for the output (O(1) extra if merging in place)."""
    if not intervals:
        return []
    ordered = sorted(intervals, key=lambda iv: iv[0])
    merged = [list(ordered[0])]
    for start, end in ordered[1:]:
        if start <= merged[-1][1]:          # overlap (use < for touching-is-not-overlap)
            merged[-1][1] = max(merged[-1][1], end)   # max: the current may CONTAIN the next
        else:
            merged.append([start, end])
    return [tuple(iv) for iv in merged]


def interval_intersection(a, b):
    """Intersect two lists of disjoint, sorted intervals with two pointers.
    The intersection of [s1,e1] and [s2,e2] is [max(s1,s2), min(e1,e2)],
    non-empty iff that lower bound <= that upper bound. Advance whichever
    interval ends first — it can never intersect anything later.
    Time O(n + m), space O(output)."""
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        lo = max(a[i][0], b[j][0])
        hi = min(a[i][1], b[j][1])
        if lo <= hi:
            out.append((lo, hi))
        if a[i][1] < b[j][1]:
            i += 1
        else:
            j += 1
    return out


assert merge_intervals([(1, 3), (2, 6), (8, 10), (15, 18)]) == [(1, 6), (8, 10), (15, 18)]
assert merge_intervals([(1, 10), (2, 3)]) == [(1, 10)]
assert interval_intersection([(0, 2), (5, 10)], [(1, 5), (8, 12)]) == [(1, 2), (5, 5), (8, 10)]

def build_prefix(nums):
    """prefix[i] = sum of the first i elements, prefix[0] = 0.
    The leading zero is what makes range_sum work without a special case.
    Build O(n), then any range query is O(1). Space O(n)."""
    prefix = [0] * (len(nums) + 1)
    for i, v in enumerate(nums):
        prefix[i + 1] = prefix[i] + v
    return prefix


def range_sum(prefix, lo, hi):
    """Sum of nums[lo:hi+1], inclusive on both ends. O(1)."""
    return prefix[hi + 1] - prefix[lo]


def subarray_sum_equals_k(nums, k):
    """Count contiguous subarrays summing to exactly k — WORKS with negatives,
    where a sliding window does not.
    sum(i..j) == k  <=>  prefix[j+1] - prefix[i] == k  <=>  prefix[i] == prefix[j+1] - k
    so at each j, count how many earlier prefixes had the required value.
    Time O(n), space O(n) for the counts."""
    counts = {0: 1}                    # the empty prefix, so subarrays starting at 0 count
    running = 0
    total = 0
    for v in nums:
        running += v
        total += counts.get(running - k, 0)
        counts[running] = counts.get(running, 0) + 1
    return total


p = build_prefix([1, 2, 3, 4, 5])
assert range_sum(p, 1, 3) == 9         # 2 + 3 + 4
assert subarray_sum_equals_k([1, 1, 1], 2) == 2
assert subarray_sum_equals_k([1, -1, 0], 0) == 3