Sliding Window & Two Pointers

🎯 Mục tiêu

Luyện tập kỹ thuật cửa sổ trượt và hai con trỏ qua bài toán tổng mảng con lớn nhất, cửa sổ nhỏ nhất chứa mẫu và chuỗi con dài nhất không lặp.

Yêu cầu

Bài 1: Tổng mảng con lớn nhất (Kadane's Algorithm)

Tìm mảng con liên tiếp có tổng lớn nhất.

def max_subarray_sum(nums: list[int]) -> int:
    """Tìm tổng lớn nhất của mảng con liên tiếp (Kadane's Algorithm)."""
    # TODO: Cài đặt
    pass

assert max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6  # [4,-1,2,1]
assert max_subarray_sum([-1, -2, -3]) == -1
assert max_subarray_sum([5, 4, -1, 7, 8]) == 23

Bài 2: Tổng lớn nhất mảng con kích thước k

Cho mảng và số k, tìm tổng lớn nhất của mảng con có đúng k phần tử.

def max_sum_subarray_k(nums: list[int], k: int) -> int:
    """Tìm tổng lớn nhất của mảng con kích thước k (cửa sổ cố định)."""
    # TODO: Cài đặt sliding window cố định
    pass

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

Bài 3: Cửa sổ nhỏ nhất chứa tất cả ký tự mẫu

Cho chuỗi s và chuỗi t, tìm cửa sổ ngắn nhất trong s chứa tất cả ký tự của t.

def min_window_substring(s: str, t: str) -> str:
    """Tìm cửa sổ ngắn nhất trong s chứa mọi ký tự của t."""
    # TODO: Cài đặt sliding window co giãn
    pass

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

Bài 4: Chuỗi con dài nhất không có ký tự lặp

Tìm độ dài chuỗi con liên tiếp dài nhất mà không có ký tự nào xuất hiện quá 1 lần.

def longest_unique_substring(s: str) -> int:
    """Tìm độ dài chuỗi con dài nhất không có ký tự lặp."""
    # TODO: Cài đặt sliding window với hash set
    pass

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

Phân tích độ phức tạp

Bài	Time	Space
1 - Kadane's	O(n)	O(1)
2 - Fixed window	O(n)	O(1)
3 - Min window substr	O(n + m)	O(m)
4 - Longest unique	O(n)	O(min(n, alphabet))

Gợi ý

Gợi ý Bài 1

Duy trì current_sum = max(nums[i], current_sum + nums[i]) và cập nhật max_sum tại mỗi bước.

Gợi ý Bài 3

Dùng hai con trỏ mở rộng right để chứa đủ ký tự, rồi thu hẹp left để tìm cửa sổ nhỏ nhất. Dùng dict đếm tần suất.

Gợi ý Bài 4

Dùng set lưu ký tự hiện tại. Khi gặp trùng, thu hẹp từ bên trái cho đến khi không còn trùng.

Lời giải tham khảo

Xem lời giải

def max_subarray_sum(nums):
    max_sum = current = nums[0]
    for num in nums[1:]:
        current = max(num, current + num)
        max_sum = max(max_sum, current)
    return max_sum
def max_sum_subarray_k(nums, k):
    window_sum = sum(nums[:k])
    max_sum = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum
def min_window_substring(s, t):
    from collections import Counter
    need = Counter(t)
    missing = len(t)
    left = start = end = 0
    for right, char in enumerate(s, 1):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1
        if missing == 0:
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if not end or right - left <= end - start:
                start, end = left, right
            need[s[left]] += 1
            missing += 1
            left += 1
    return s[start:end]
def longest_unique_substring(s):
    char_set = set()
    left = max_len = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

📚 Bài liên quan

• Kỹ thuật cửa sổ trượt
• Kỹ thuật hai con trỏ