Tìm hiểu Two Pointer và Sliding Window

“Bí quyết không nằm ở việc di chuyển con trỏ — mà ở việc KHÔNG BAO GIỜ lùi lại. Mỗi con trỏ chỉ tiến, tổng quãng đường là O(n). Đó là lý do một vòng lặp lồng nhau lại chạy nhanh như một vòng.”

Đây là quyển thứ sáu. Nếu Sliding Window là “con dao mổ trâu” biến vô số bài O(n²) thành O(n), thì quyển này sẽ dạy bạn vì sao con dao đó sắc — không chỉ thuộc template, mà hiểu phân tích khấu hao khiến nó nhanh và điều kiện đơn điệu khiến nó đúng.

Phần 0 — Tư tưởng cốt lõi: đừng quay lại

Two Pointers và Sliding Window là hai kỹ thuật dùng vài chỉ số (con trỏ) cùng quét qua một mảng/chuỗi, để tránh vòng lặp lồng nhau O(n²).

• Two Pointers (con trỏ đôi): hai chỉ số di chuyển qua dữ liệu — có thể từ hai đầu vào giữa, hoặc cùng chiều với tốc độ khác nhau.
• Sliding Window (cửa sổ trượt): giữ một đoạn liên tục [left, right] và cho nó “trượt” — mở rộng bên phải, thu hẹp bên trái tùy điều kiện.

Bí mật chung: tính đơn điệu + không lùi

Điều khiến hai kỹ thuật này hoạt động là dữ liệu có tính đơn điệu: khi dịch con trỏ theo một hướng, “trạng thái” thay đổi theo một chiều dự đoán được. Nhờ vậy ta không bao giờ cần lùi con trỏ lại — mỗi con trỏ chỉ tiến về phía trước.

Phần 1 — Vì sao O(n)? Phân tích khấu hao

Đây là hiểu biết phân định “biết template” với “hiểu bản chất”. Nhìn code sliding window, ta thấy một vòng for lồng một vòng while — trông như O(n²). Nhưng nó thực sự là O(n). Vì sao?

for right in range(n):        # vòng ngoài chạy n lần
    ...
    while điều_kiện:          # vòng trong — trông đáng sợ!
        left += 1
    ...

Chìa khóa: con trỏ left chỉ TĂNG, không bao giờ giảm, và bị chặn bởi n. Nghĩa là qua toàn bộ thuật toán, left được tăng tối đa n lần tổng cộng — chứ không phải n lần mỗi vòng ngoài.

• Vòng ngoài (right): chạy n lần → O(n).
• Vòng trong (left): tổng số lần chạy qua tất cả các vòng ngoài cộng lại ≤ n → O(n).
• Tổng: O(n) + O(n) = O(n). ✓

Đây gọi là phân tích khấu hao (amortized analysis): một thao tác lẻ có thể tốn nhiều, nhưng trung bình trên cả quá trình thì rẻ, vì tổng công việc bị chặn.

Phần A

Two Pointers

Con trỏ đôi — ba biến thể và khi nào dùng.

A.1 — Ba biến thể

A.2 — Đối đầu: mảng sắp / palindrome / two-sum

Hai con trỏ left (từ đầu) và right (từ cuối) tiến về giữa. Điều kiện tiên quyết: dữ liệu thường phải ĐÃ SẮP XẾP (để việc dịch con trỏ có tác dụng đơn điệu lên “trạng thái”).

Two Sum trên mảng đã sắp:

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1               # cần tổng LỚN hơn → dịch trái sang phải
        else:
            right -= 1              # cần tổng NHỎ hơn → dịch phải sang trái
    return None

Vì sao đúng: mảng đã sắp nên nums[left]+nums[right] phản ứng đơn điệu với việc dịch con trỏ — dịch left chỉ làm tổng tăng, dịch right chỉ làm tổng giảm. Ta luôn biết dịch bên nào. O(n) thay vì O(n²) của hai vòng lồng.

Kiểm tra palindrome:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Container With Most Water (mang hơi hướng greedy):

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        best = max(best, area)
        if height[left] < height[right]:   # ⭐ dịch cột THẤP hơn
            left += 1
        else:
            right -= 1
    return best

3Sum (sắp xếp + đối đầu):

def three_sum(nums):
    nums.sort()                     # ⭐ sắp trước để dùng two pointers
    res, n = [], len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue                # bỏ trùng cho phần tử neo
        left, right = i + 1, n - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                res.append([nums[i], nums[left], nums[right]])
                left += 1; right -= 1
                while left < right and nums[left] == nums[left-1]:
                    left += 1       # bỏ trùng
                while left < right and nums[right] == nums[right+1]:
                    right -= 1
            elif s < 0:
                left += 1
            else:
                right -= 1
    return res

Từ O(n³) (ba vòng lồng) xuống O(n²) (một vòng ngoài + two pointers).

A.3 — Nhanh-chậm: tại chỗ / chu trình linked list

Hai con trỏ cùng chiều, một nhanh một chậm. slow thường đánh dấu “ranh giới phần đã xử lý”, fast quét tới.

Xóa phần tử trùng tại chỗ (mảng đã sắp):

def remove_duplicates(nums):
    if not nums: return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]     # slow = cuối phần kết quả không trùng
    return slow + 1

Dồn số 0 về cuối:

def move_zeroes(nums):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1                   # slow = vị trí đặt số khác 0 tiếp theo

Phát hiện chu trình trong linked list (Floyd’s — rùa & thỏ):

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # đi 1 bước
        fast = fast.next.next       # đi 2 bước
        if slow == fast:            # ⭐ gặp nhau → CÓ chu trình
            return True
    return False

🔗 Nối với Bí kíp Graph: đây chính là phát hiện chu trình bằng hai con trỏ! Nếu có vòng, con thỏ (nhanh) sẽ “đuổi kịp” con rùa (chậm) từ phía sau trong vòng. Floyd’s là phiên bản two-pointer của bài phát hiện chu trình, chỉ tốn O(1) bộ nhớ.

A.4 — Hai con trỏ trên hai mảng (merge)

Mỗi con trỏ quét một mảng đã sắp, so sánh và tiến con trỏ nhỏ hơn — chính là bước “trộn” của Merge Sort:

def merge_sorted(a, b):
    i, j, result = 0, 0, []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:])                # phần dư của mảng còn lại
    result.extend(b[j:])
    return result

Đại diện: Merge Two Sorted Lists, Intersection of Two Arrays, Merge Sorted Array. O(n+m).

A.5 — Khi nào Two Pointers hoạt động

• ✅ Dữ liệu đã sắp xếp (hoặc có thể sắp) — để dịch con trỏ có tác dụng đơn điệu (đối đầu).
• ✅ Bài về cặp / bộ ba thỏa điều kiện tổng (two-sum, 3sum, 4sum).
• ✅ Palindrome hoặc đối xứng (đối đầu).
• ✅ Sửa mảng tại chỗ (O(1) bộ nhớ): xóa/dồn phần tử (nhanh-chậm).
• ✅ Chu trình / điểm giữa linked list (nhanh-chậm).
• ✅ Trộn / giao / hợp hai dãy đã sắp (hai mảng).

⚠️ Điều kiện cốt tử: two pointers (đối đầu) cần tính đơn điệu — dịch con trỏ phải làm “trạng thái” thay đổi theo hướng dự đoán được. Đó là lý do mảng thường phải đã sắp. Không có tính đơn điệu → two pointers không áp dụng được.

Phần B

Sliding Window

Cửa sổ trượt — template vạn năng và các biến tấu.

B.1 — Hai loại: cố định vs biến đổi

Sliding Window giải các bài về đoạn/đoạn con liên tục (contiguous subarray/substring). Có hai loại:

Chữ ký nhận diện sliding window: đề nói về “đoạn con LIÊN TỤC” (không phải dãy con rời rạc — đó là DP/LIS) + hỏi “dài nhất / ngắn nhất / đếm số đoạn thỏa điều kiện”.

B.2 — TEMPLATE VẠN NĂNG cho cửa sổ biến đổi

Đây là phần vàng nhất của Phần B. Gần như mọi bài sliding window biến đổi đều khớp khuôn ba bước sau. Học thuộc là xử được cả một lớp bài khổng lồ.

def sliding_window(s):
    window = {}                     # trạng thái cửa sổ (đếm ký tự, tổng, số phần tử khác nhau...)
    left = 0
    result = 0                      # hoặc float('inf') cho bài "ngắn nhất"

    for right in range(len(s)):
        # ── BƯỚC 1: MỞ RỘNG — thêm s[right] vào cửa sổ ──
        thêm s[right] vào window

        # ── BƯỚC 2: THU HẸP — khi cửa sổ VI PHẠM, co left ──
        while cửa_sổ_vi_phạm_điều_kiện:
            bỏ s[left] khỏi window
            left += 1

        # ── BƯỚC 3: CẬP NHẬT đáp án (cửa sổ [left, right] giờ hợp lệ) ──
        result = max(result, right - left + 1)

    return result

        left                    right
         │                        │
   ┌─────┼────────────────────────┼─────┐
   │     [  cửa sổ hợp lệ hiện tại ]     │
   └─────┼────────────────────────┼─────┘
         │                        │
    co lại khi           mở rộng mỗi bước
    vi phạm              (right luôn tiến)

Ví dụ — Chuỗi con dài nhất không lặp ký tự

def length_of_longest_substring(s):
    window = set()
    left = best = 0
    for right in range(len(s)):
        while s[right] in window:       # VI PHẠM: có ký tự trùng
            window.remove(s[left])      # co left cho tới khi hết trùng
            left += 1
        window.add(s[right])            # giờ thêm được an toàn
        best = max(best, right - left + 1)
    return best

Biến tấu “ngắn nhất” — Minimum Window Substring (khó hơn)

Khi hỏi đoạn ngắn nhất, cấu trúc đảo lại: mở rộng cho tới khi hợp lệ, rồi co lại để tối thiểu hóa:

from collections import Counter

def min_window(s, t):
    need = Counter(t)
    missing = len(t)                    # số ký tự còn thiếu
    left = 0
    best, best_len = "", float('inf')
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:             # ⭐ cửa sổ ĐÃ chứa đủ t → co để tối thiểu
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best = s[left:right+1]
            need[s[left]] += 1
            if need[s[left]] > 0:       # bỏ đi thì lại thiếu
                missing += 1
            left += 1
    return best

B.3 — Cửa sổ cố định

Khi kích thước k cố định, không cần co giãn — chỉ “trượt”: thêm phần tử mới bên phải, bỏ phần tử cũ bên trái.

def max_sum_subarray(nums, k):
    window_sum = sum(nums[:k])          # cửa sổ đầu tiên
    best = window_sum
    for right in range(k, len(nums)):
        window_sum += nums[right] - nums[right - k]   # ⭐ thêm mới, BỎ cũ
        best = max(best, window_sum)
    return best

B.4 — Đếm cửa sổ: mẹo “at most K”

Bài “đếm số đoạn con thỏa đúng K điều kiện” thường khó trực tiếp. Mẹo thần thánh:

Đúng K = (Tối đa K) − (Tối đa K−1)

Vì “tối đa K” dễ đếm bằng sliding window, còn phép trừ khử đi phần “tối đa K−1”, để lại đúng phần “đúng K”.

from collections import defaultdict

def at_most_k_distinct(nums, k):        # số đoạn con có TỐI ĐA k phần tử khác nhau
    count = defaultdict(int)
    left = result = 0
    for right in range(len(nums)):
        count[nums[right]] += 1
        while len(count) > k:           # vi phạm: quá k loại
            count[nums[left]] -= 1
            if count[nums[left]] == 0:
                del count[nums[left]]
            left += 1
        result += right - left + 1      # ⭐ số đoạn con hợp lệ KẾT THÚC tại right
    return result

def exactly_k_distinct(nums, k):
    return at_most_k_distinct(nums, k) - at_most_k_distinct(nums, k - 1)

B.5 — Sliding Window Maximum (monotonic deque)

Bài kinh điển: tìm giá trị lớn nhất trong mỗi cửa sổ trượt kích thước k. Dùng deque đơn điệu (monotonic deque) lưu chỉ số theo giá trị giảm dần.

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()                        # lưu CHỈ SỐ, giá trị giảm dần từ đầu → cuối
    result = []
    for i in range(len(nums)):
        if dq and dq[0] <= i - k:       # bỏ chỉ số đã trượt khỏi cửa sổ (ở đầu)
            dq.popleft()
        while dq and nums[dq[-1]] < nums[i]:   # bỏ các giá trị nhỏ hơn nums[i] (vô dụng)
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])  # ⭐ đầu deque luôn là MAX của cửa sổ
    return result

Vì sao O(n): mỗi chỉ số vào deque đúng 1 lần và ra tối đa 1 lần → tổng thao tác O(n) (lại là phân tích khấu hao!).

🔗 Nối với Bí kíp DP: đây chính là kỹ thuật “tối ưu hàng đợi đơn điệu (monotonic queue)” — thứ biến nhiều công thức chuyển DP O(n²) thành O(n). Sliding window maximum là dạng thuần túy của nó.

Phần C

Two Pointers vs Sliding Window vs Prefix Sum

Ba anh em “quét mảng”. Chọn đúng công cụ là nửa lời giải.

⚠️ RANH GIỚI QUAN TRỌNG — sliding window và số âm: Sliding window dựa vào giả định “thêm phần tử làm cửa sổ ‘tệ’ hơn theo một chiều”. Với số âm, giả định này sụp đổ — thêm một số âm có thể làm tổng giảm, phá vỡ tính đơn điệu. Ví dụ bài “đếm đoạn con có tổng = K” với số âm: sliding window SAI, phải dùng prefix sum + hashmap:

def subarray_sum_equals_k(nums, k):
    from collections import defaultdict
    prefix, count = 0, defaultdict(int)
    count[0] = 1                    # tổng tiền tố rỗng
    result = 0
    for x in nums:
        prefix += x
        result += count[prefix - k] # có bao nhiêu tiền tố trước cho ra tổng đoạn = k
        count[prefix] += 1
    return result

Đây là cạm bẫy cực phổ biến: thấy “đoạn con” liền phản xạ sliding window, nhưng nếu có số âm → phải prefix sum. Ghi nhớ ranh giới này!

Phần D

☠️ Cạm bẫy chết người

💀 Bẫy #1: Sliding Window với số âm

Kỹ thuật giả định tính đơn điệu, số âm phá vỡ nó. “Tổng đoạn con = K” có số âm → dùng prefix sum + hashmap, không phải sliding window.

💀 Bẫy #2: Lệch 1 ở kích thước cửa sổ

Kích thước cửa sổ [left, right] là right - left + 1 (có +1!). Quên +1 là lỗi kinh điển. Kiểm tra bằng ví dụ nhỏ: left=right → kích thước 1.

💀 Bẫy #3: Sai THỨ TỰ ba bước

Trong template: mở rộng → thu hẹp → cập nhật. Với bài “dài nhất”, cập nhật sau khi thu hẹp (cửa sổ mới hợp lệ). Cập nhật sai chỗ → tính cả cửa sổ vi phạm.

💀 Bẫy #4: Two pointers trên mảng CHƯA sắp

Two pointers đối đầu cần tính đơn điệu (thường là mảng đã sắp). Quên sắp trước khi chạy 3Sum/two-sum-sorted → kết quả sai.

💀 Bẫy #5: Quên xử lý phần tử trùng (3Sum, 4Sum)

Không bỏ trùng → sinh ra các bộ lặp lại. Nhớ các dòng while ... nums[left] == nums[left-1]: left += 1.

💀 Bẫy #6: Fast-slow trên linked list — quên kiểm tra null

fast.next.next sẽ lỗi nếu fast hoặc fast.next là None. Luôn kiểm tra while fast and fast.next trước.

💀 Bẫy #7: Nhầm “đoạn con liên tục” với “dãy con rời rạc”

Sliding window chỉ cho đoạn LIÊN TỤC. Nếu đề cho phép bỏ phần tử ở giữa (dãy con rời rạc, subsequence) → đó là DP (như LIS), không phải sliding window.

Phần E

🔗 Nối với bộ sách

1. Two Pointers ~ tư duy Greedy. “Luôn dịch cột thấp hơn” (Container With Most Water) là một lập luận greedy — loại bỏ lựa chọn không thể tối ưu.
2. Fast-slow ~ phát hiện chu trình. Floyd’s rùa-thỏ là phiên bản two-pointer của bài phát hiện chu trình trong đồ thị — chỉ tốn O(1) bộ nhớ.
3. Sliding Window Maximum = monotonic queue. Chính là kỹ thuật tối ưu DP, thứ hạ O(n²) xuống O(n).
4. Prefix Sum — cũng là một tối ưu DP, và là “cứu tinh” khi sliding window gặp số âm.
5. Tính đơn điệu ~ Binary Search. Điều kiện “đơn điệu” khiến two pointers/sliding window hoạt động cùng bản chất với điều kiện khiến binary search hoạt động — cả ba đều khai thác cấu trúc đơn điệu để bỏ qua công việc thừa.

Phần F

📋 Bảng tra cứu thần tốc

Bốn câu hỏi khi gặp bài mảng/chuỗi: (1) Đoạn con LIÊN TỤC hay rời rạc? (2) Có số âm không? (3) Dữ liệu đã sắp chưa? (4) Hỏi cặp/bộ (→two pointers) hay đoạn dài-ngắn (→sliding window)?

Phần G

🎯 Lộ trình luyện tập theo cấp độ

Tên bài theo phong cách LeetCode.

🟢 Cấp 1 — Nhập môn

• Two Sum II (Input Array Is Sorted) — two pointers đối đầu cơ bản nhất.
• Valid Palindrome — đối đầu, kiểm tra đối xứng.
• Move Zeroes / Remove Duplicates from Sorted Array — fast-slow tại chỗ.
• Maximum Average Subarray I — cửa sổ cố định.

🟡 Cấp 2 — Vận dụng

• Longest Substring Without Repeating Characters — template sliding window kinh điển, phải nắm.
• 3Sum — sắp xếp + two pointers, xử lý trùng.
• Container With Most Water — đối đầu mang tính greedy.
• Fruit Into Baskets — sliding window “tối đa 2 loại” (chính là at-most-K).
• Linked List Cycle — Floyd’s rùa-thỏ.

🔴 Cấp 3 — Nâng cao

• Minimum Window Substring — sliding window “ngắn nhất”, biến tấu khó.
• Longest Repeating Character Replacement — cửa sổ với điều kiện tinh tế.
• Subarrays with K Different Integers — mẹo đúng K = atMost(K) − atMost(K−1).
• Sliding Window Maximum — monotonic deque.
• Subarray Sum Equals K — ⚠️ bẫy số âm, phải dùng prefix sum + hashmap (không phải sliding window!).

⚫ Cấp trùm cuối

• Minimum Number of K Consecutive Bits Flips — sliding window + kỹ thuật lật khéo.
• Count Number of Nice Subarrays — atMost-K trên tính chẵn lẻ.
• Trapping Rain Water — two pointers đối đầu nâng cao (hoặc stack).
• Find All Anagrams in a String — cửa sổ cố định + đếm ký tự.
• Chứng minh bằng tay: vì sao sliding window là O(n) (khấu hao); vì sao nó hỏng với số âm.

🏋️ Nguyên tắc luyện tập: với mỗi bài, trước khi code hãy trả lời bốn câu hỏi ở Phần F. Đặc biệt hai câu tối quan trọng: “Có số âm không?” (quyết định sliding window hay prefix sum) và “Liên tục hay rời rạc?” (quyết định sliding window hay DP). Chọn nhầm công cụ ngay từ đầu là sai từ gốc.

🎓 Lời kết — Tâm pháp Two Pointers & Sliding Window

Gói toàn bộ bí kíp vào năm câu tâm pháp:

1. Con trỏ chỉ tiến, không bao giờ lùi. Đó là lý do một vòng lặp lồng nhau lại chạy O(n) — hãy đếm tổng bước con trỏ, đừng đếm vòng lặp.
2. Sliding Window là Two Pointers cùng chiều. Học chung một tư tưởng “quét một lần”; template 3 bước xử được cả một lớp bài.
3. Đơn điệu là điều kiện sống còn. Two pointers cần mảng đã sắp; sliding window cần “cửa sổ đơn điệu” (thường là giá trị không âm). Mất đơn điệu → mất kỹ thuật.
4. Số âm là kẻ phá bĩnh. “Tổng đoạn con = K” có số âm → sliding window hỏng, chuyển sang prefix sum + hashmap. Đây là bẫy giết nhiều người nhất.
5. Phân biệt liên tục vs rời rạc. Đoạn con liên tục → sliding window; dãy con rời rạc → DP. Nhìn nhầm là sai từ gốc.

Luyện đủ bốn cấp ở Phần G, mỗi bài đều tự hỏi bốn câu định hình — sau khoảng 30–40 bài, bạn sẽ “ngửi” ra ngay bài nào là two pointers, bài nào sliding window, và bài nào là cái bẫy prefix-sum trá hình. Đó là lúc bạn đã làm chủ nghệ thuật quét một lần. 🎯