Kỹ thuật hai con trỏ (two pointers) và cửa sổ trượt (sliding window)

Các kỹ thuật này giải quyết vấn đề gì

Nhiều bài toán mảng và chuỗi hỏi về các cặp hoặc đoạn liên tiếp: hai số có tổng bằng một giá trị cho trước, chuỗi con dài nhất không có ký tự lặp, mảng con ngắn nhất có tổng ít nhất k. Kiểm tra mọi cặp hoặc mọi đoạn tốn O(n²) hoặc hơn. Hai con trỏ tránh điều này bằng cách tận dụng một tính chất của dữ liệu, như thứ tự đã sắp xếp hoặc việc cửa sổ chỉ cần cập nhật nhỏ, để loại bỏ nhiều ứng viên cùng lúc.

Con trỏ hai đầu: tổng cặp trong mảng đã sắp xếp

Tìm hai số trong danh sách đã sắp xếp [1, 3, 4, 6, 8, 11] có tổng bằng 10. Bắt đầu từ số nhỏ nhất và lớn nhất. Nếu tổng quá nhỏ, cách duy nhất để tăng là dịch left sang phải; nếu quá lớn, dịch right sang trái.

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return left, right
        if s < target:
            left += 1
        else:
            right -= 1
    return None
print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))   # (2, 3)
print(pair_with_sum([1, 3, 4, 6, 8, 11], 2))    # None

Mỗi bước dịch một con trỏ vào trong, nên có tối đa n − 1 bước: O(n) thời gian và O(1) không gian. Cùng khuôn này kiểm tra chuỗi có là palindrome không, đảo ngược mảng tại chỗ, và khi đặt trong một vòng lặp ngoài thì giải 3Sum trong O(n²) thay vì O(n³).

Con trỏ nhanh và chậm: lọc tại chỗ

Con trỏ chậm đánh dấu nơi phần tử được giữ tiếp theo sẽ nằm; con trỏ nhanh quét qua mọi phần tử. Cách này xóa phần tử trùng khỏi list đã sắp xếp mà không cần thêm bộ nhớ.

def dedupe_sorted(nums):
    """Remove duplicates in place; return the new length."""
    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]
    return slow + 1
a = [1, 1, 2, 3, 3, 3, 5]
k = dedupe_sorted(a)
print(k, a[:k])   # 4 [1, 2, 3, 5]

Trên danh sách liên kết, con trỏ nhanh đi hai nút mỗi bước còn con trỏ chậm đi một nút. Nếu chúng gặp nhau thì danh sách có chu trình (phát hiện chu trình của Floyd); khi con trỏ nhanh tới cuối, con trỏ chậm đang ở giữa.

Cửa sổ trượt: chuỗi con dài nhất không lặp ký tự

Cửa sổ trượt giữ đoạn s[left:right + 1] luôn hợp lệ. Dịch right tiến từng ký tự một. Khi ký tự mới phá vỡ quy tắc, dịch left tiến cho đến khi cửa sổ hợp lệ trở lại. Ghi nhận cửa sổ tốt nhất trong quá trình đó.

def longest_unique(s):
    last_seen = {}          # char -> last index
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1   # jump past the repeat
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best
print(longest_unique("abcabcbb"))   # 3  ("abc")
print(longest_unique("pwwkew"))     # 3  ("wke")
print(longest_unique(""))           # 0

Cửa sổ có hai loại. Cửa sổ kích thước cố định k phần tử thêm phần tử đi vào bên phải và bỏ phần tử đi ra bên trái, ví dụ để tính trung bình trượt. Cửa sổ kích thước thay đổi giãn ra và co lại để thỏa một điều kiện, như ở trên.

def min_len_subarray(nums, k):
    """Shortest subarray with sum >= k (non-negative nums)."""
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= k:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best
print(min_len_subarray([2, 3, 1, 2, 4, 3], 7))   # 2  ([4, 3])

Độ phức tạp thời gian và không gian

Lý do cửa sổ trượt là O(n) dù có vòng while lồng bên trong: left và right mỗi con trỏ chỉ tiến tối đa n lần tính tổng cộng, nên tổng công việc nhiều nhất là 2n bước.

Lỗi thường gặp

• Dùng con trỏ hai đầu trên dữ liệu chưa sắp xếp. Quyết định dịch trái hay phải chỉ đúng nhờ mảng đã được sắp xếp.
• Dùng cửa sổ trượt theo tổng khi các số có thể âm. Thu hẹp cửa sổ không còn luôn làm giảm tổng; hãy dùng tổng tiền tố với bảng băm thay thế.
• Sai lệch một khi tính độ dài cửa sổ: cửa sổ left..right tính cả hai đầu có right - left + 1 phần tử.
• Quên dừng ở left < right, khiến một phần tử ghép cặp với chính nó.
• Dịch left lùi lại. Trong ví dụ chuỗi con, phép kiểm tra last_seen[ch] >= left ngăn việc nhảy ngược về vị trí cũ.

Khi nào dùng và các câu hỏi phỏng vấn điển hình

Hãy nghĩ đến hai con trỏ khi đầu vào đã sắp xếp (hoặc sắp xếp rẻ) và bạn tìm các cặp, hoặc khi cần sửa mảng tại chỗ. Hãy nghĩ đến cửa sổ trượt khi đề nói mảng con hoặc chuỗi con liên tiếp và hỏi dài nhất, ngắn nhất, lớn nhất hoặc số lượng với điều kiện thay đổi có quy luật khi cửa sổ giãn ra. Nếu dữ liệu chưa sắp xếp và bạn cần một cặp, hash set thường đơn giản hơn và cũng là O(n).

• Two Sum II (đầu vào đã sắp xếp), 3Sum, Container With Most Water, Trapping Rain Water.
• Valid Palindrome, Reverse String, Move Zeroes, Remove Duplicates from Sorted Array.
• Longest Substring Without Repeating Characters, Minimum Window Substring, Sliding Window Maximum (với deque).
• Linked List Cycle, Middle of the Linked List.

Ngoài phỏng vấn, các ý tưởng này xuất hiện khi trộn các tệp đã sắp xếp, trong giao thức mạng theo dõi một cửa sổ các gói chưa được xác nhận (cửa sổ trượt TCP), bộ giới hạn tốc độ đếm sự kiện trong N giây gần nhất, và trung bình trượt trong chuỗi thời gian.