Sliding Window — Kỹ thuật cửa sổ trượt

Hệ thống streaming analytics của Kafka xử lý hàng triệu event mỗi giây. Mỗi khi cần tính "trung bình số lượng request trong 5 phút gần nhất", nếu tính lại từ đầu mỗi giây thì server sẽ chết trước khi trả kết quả. Thay vào đó, Kafka chỉ trừ event cũ nhất và cộng event mới nhất — đó chính là Sliding Window.

Kỹ thuật này biến bài toán $O (N \times K)$ thành $O (N)$ bằng một ý tưởng đơn giản: không tính lại từ đầu, chỉ cập nhật phần thay đổi. Trong phỏng vấn kỹ thuật, hơn 20% bài toán dạng subarray/substring có thể giải bằng Sliding Window. Trong production, nó là xương sống của rate limiting, moving average, và network flow control.

Nếu bạn từng viết hai vòng for lồng nhau để duyệt mọi subarray rồi tự hỏi "có cách nào nhanh hơn không?" — câu trả lời nằm ở đây.

Bức tranh tư duy

Hình dung bạn đang ngồi trên xe buýt ở Sài Gòn, nhìn qua cửa sổ. Cửa sổ chỉ cho bạn thấy một đoạn phố tại mỗi thời điểm. Khi xe di chuyển, cửa sổ trượt sang phải — tòa nhà cũ biến mất ở bên trái, tòa nhà mới xuất hiện ở bên phải.

Bạn không cần đi lại từ đầu phố để đếm lại toàn bộ cửa hàng. Mỗi lần cửa sổ trượt, bạn chỉ cần trừ cửa hàng vừa mất khỏi tầm nhìn và cộng cửa hàng mới xuất hiện.

text

Mảng:    [2, 1, 5, 1, 3, 2, 8]     K = 3

Bước 1:  [2, 1, 5] 1, 3, 2, 8     tổng = 8
          L     R

Bước 2:   2,[1, 5, 1] 3, 2, 8     tổng = 8 - 2 + 1 = 7
             L     R

Bước 3:   2, 1,[5, 1, 3] 2, 8     tổng = 7 - 1 + 3 = 9  ← max
                L     R

Bước 4:   2, 1, 5,[1, 3, 2] 8     tổng = 9 - 5 + 2 = 6
                   L     R

Hai biến thể chính: cửa sổ cố định (fixed-size — kích thước K không đổi) và cửa sổ co giãn (variable-size — mở rộng/thu hẹp tùy điều kiện). Fixed window giống cửa sổ xe buýt — luôn cùng kích thước. Variable window giống ống nhòm zoom — phóng to thu nhỏ để tìm đối tượng phù hợp.

📌 Khi nào analogy không còn chính xác

Cửa sổ xe buýt chỉ trượt một chiều. Trong variable-size window, con trỏ left có thể "nhảy" nhiều bước liên tiếp khi thu hẹp — không phải lúc nào cũng trượt đều. Tổng số bước vẫn là $O (N)$ vì mỗi phần tử chỉ vào/ra window tối đa một lần.

Cốt lõi kỹ thuật

Fixed-Size Window — Cửa sổ cố định

Áp dụng khi đề bài cho trước kích thước window K. Hai con trỏ left và right luôn cách nhau đúng K vị trí.

C++PythonJavaGo

cpp

// Tổng lớn nhất của subarray kích thước K
int maxSumSubarrayK(const vector<int>& arr, int k) {
    if ((int)arr.size() < k) return 0;

    int windowSum = 0;
    for (int i = 0; i < k; i++)
        windowSum += arr[i];

    int maxSum = windowSum;
    for (int i = k; i < (int)arr.size(); i++) {
        windowSum += arr[i] - arr[i - k];   // cộng mới, trừ cũ
        maxSum = max(maxSum, windowSum);
    }
    return maxSum;
}

python

def max_sum_subarray_k(arr: list[int], k: int) -> int:
    """Tổng lớn nhất của subarray kích thước K — O(N)."""
    if len(arr) < k:
        return 0

    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

java

static int maxSumSubarrayK(int[] arr, int k) {
    if (arr.length < k) return 0;

    int windowSum = 0;
    for (int i = 0; i < k; i++)
        windowSum += arr[i];

    int maxSum = windowSum;
    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

func maxSumSubarrayK(arr []int, k int) int {
    if len(arr) < k {
        return 0
    }

    windowSum := 0
    for i := 0; i < k; i++ {
        windowSum += arr[i]
    }

    maxSum := windowSum
    for i := k; i < len(arr); i++ {
        windowSum += arr[i] - arr[i-k]
        if windowSum > maxSum {
            maxSum = windowSum
        }
    }
    return maxSum
}

Variable-Size Window — Cửa sổ co giãn

Áp dụng khi đề bài yêu cầu tìm subarray ngắn nhất/dài nhất thỏa điều kiện. Con trỏ right mở rộng window, left thu hẹp khi điều kiện đã thỏa mãn.

C++PythonJavaGo

cpp

// Subarray ngắn nhất có tổng >= target
int smallestSubarrayWithSum(const vector<int>& arr, int target) {
    int minLen = INT_MAX;
    int windowSum = 0, left = 0;

    for (int right = 0; right < (int)arr.size(); right++) {
        windowSum += arr[right];

        while (windowSum >= target) {
            minLen = min(minLen, right - left + 1);
            windowSum -= arr[left++];
        }
    }
    return minLen == INT_MAX ? 0 : minLen;
}

python

def smallest_subarray_with_sum(arr: list[int], target: int) -> int:
    """Subarray ngắn nhất có tổng >= target — O(N)."""
    min_len = float('inf')
    window_sum = 0
    left = 0

    for right in range(len(arr)):
        window_sum += arr[right]

        while window_sum >= target:
            min_len = min(min_len, right - left + 1)
            window_sum -= arr[left]
            left += 1

    return min_len if min_len != float('inf') else 0

java

static int smallestSubarrayWithSum(int[] arr, int target) {
    int minLen = Integer.MAX_VALUE;
    int windowSum = 0, left = 0;

    for (int right = 0; right < arr.length; right++) {
        windowSum += arr[right];

        while (windowSum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            windowSum -= arr[left++];
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

func smallestSubarrayWithSum(arr []int, target int) int {
    minLen := math.MaxInt32
    windowSum, left := 0, 0

    for right := 0; right < len(arr); right++ {
        windowSum += arr[right]

        for windowSum >= target {
            if right-left+1 < minLen {
                minLen = right - left + 1
            }
            windowSum -= arr[left]
            left++
        }
    }
    if minLen == math.MaxInt32 {
        return 0
    }
    return minLen
}

Sliding Window + HashMap — Bài toán chuỗi

Kết hợp window với bảng tần suất ký tự để giải bài toán substring. Đây là biến thể phổ biến nhất trong phỏng vấn.

C++PythonJavaGo

cpp

// Chuỗi con dài nhất có tối đa K ký tự phân biệt
int longestSubstringKDistinct(const string& s, int k) {
    unordered_map<char, int> freq;
    int maxLen = 0, left = 0;

    for (int right = 0; right < (int)s.size(); right++) {
        freq[s[right]]++;

        while ((int)freq.size() > k) {
            if (--freq[s[left]] == 0)
                freq.erase(s[left]);
            left++;
        }
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

python

from collections import defaultdict

def longest_substring_k_distinct(s: str, k: int) -> int:
    """Chuỗi con dài nhất có tối đa K ký tự phân biệt — O(N)."""
    freq: dict[str, int] = defaultdict(int)
    max_len = 0
    left = 0

    for right in range(len(s)):
        freq[s[right]] += 1

        while len(freq) > k:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

java

static int longestSubstringKDistinct(String s, int k) {
    Map<Character, Integer> freq = new HashMap<>();
    int maxLen = 0, left = 0;

    for (int right = 0; right < s.length(); right++) {
        freq.merge(s.charAt(right), 1, Integer::sum);

        while (freq.size() > k) {
            char leftChar = s.charAt(left);
            freq.merge(leftChar, -1, Integer::sum);
            if (freq.get(leftChar) == 0) freq.remove(leftChar);
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

func longestSubstringKDistinct(s string, k int) int {
    freq := make(map[byte]int)
    maxLen, left := 0, 0

    for right := 0; right < len(s); right++ {
        freq[s[right]]++

        for len(freq) > k {
            freq[s[left]]--
            if freq[s[left]] == 0 {
                delete(freq, s[left])
            }
            left++
        }
        if right-left+1 > maxLen {
            maxLen = right - left + 1
        }
    }
    return maxLen
}

Thực chiến

Tình huống: Rate Limiting với Sliding Window Log

Bối cảnh: API gateway cần đếm số request của mỗi user trong 60 giây gần nhất. Nếu vượt 100 request → reject. Đây là kỹ thuật Sliding Window Log — biến thể production của sliding window.

Mục tiêu: Triển khai rate limiter chính xác hơn fixed window counter, tránh edge case "burst ở ranh giới window".

python

import time
from collections import deque
from threading import Lock


class SlidingWindowRateLimiter:
    """Rate limiter dùng sliding window log — chính xác hơn fixed counter."""

    def __init__(self, max_requests: int, window_seconds: float) -> None:
        self.max_requests = max_requests
        self.window_seconds = window_seconds
        self._timestamps: dict[str, deque[float]] = {}
        self._lock = Lock()

    def allow(self, client_id: str) -> bool:
        now = time.monotonic()

        with self._lock:
            if client_id not in self._timestamps:
                self._timestamps[client_id] = deque()

            window = self._timestamps[client_id]

            # Loại bỏ timestamp ngoài cửa sổ
            while window and window[0] <= now - self.window_seconds:
                window.popleft()

            if len(window) < self.max_requests:
                window.append(now)
                return True
            return False

Phân tích:

Chọn deque thay vì list vì popleft() là $O (1)$ so với list.pop(0) là $O (N)$
time.monotonic() thay vì time.time() để tránh clock drift khi NTP đồng bộ
Thread-safe nhờ Lock — cần thiết khi nhiều request đồng thời

Tình huống: Streaming Analytics — Moving Average

Bối cảnh: Dashboard monitoring cần hiển thị "CPU usage trung bình 5 phút" cập nhật mỗi giây, xử lý hàng nghìn metric stream cùng lúc.

python

from collections import deque


class MovingAverage:
    """Fixed-size sliding window cho streaming data."""

    def __init__(self, window_size: int) -> None:
        self._window: deque[float] = deque(maxlen=window_size)
        self._sum: float = 0.0

    def add(self, value: float) -> float:
        if len(self._window) == self._window.maxlen:
            self._sum -= self._window[0]
        self._window.append(value)
        self._sum += value
        return self._sum / len(self._window)

Phân tích:

deque(maxlen=K) tự động loại phần tử cũ nhất khi đầy — không cần quản lý thủ công
Duy trì _sum tích lũy thay vì sum(window) mỗi lần — $O (1)$ thay vì $O (K)$
Floating-point accumulation error có thể tích lũy sau hàng triệu phép tính — production system cần recalibrate _sum định kỳ

Sai lầm điển hình

❌ Sai lầm 1: Dùng brute-force khi có thể slide

Vấn đề: Không nhận ra bài toán thuộc dạng Sliding Window, viết hai vòng for lồng nhau.

python

# SAI: O(N*K) — tính lại toàn bộ window mỗi lần
def max_sum_k(arr, k):
    max_sum = 0
    for i in range(len(arr) - k + 1):
        max_sum = max(max_sum, sum(arr[i:i+k]))
    return max_sum

Tại sao sai: Với N = 1,000,000 và K = 1,000, brute-force thực hiện 1 tỷ phép cộng. Sliding window chỉ cần 1 triệu phép cộng-trừ. Trong production analytics pipeline, sự khác biệt là giữa response 10ms và 10 giây.

python

# ĐÚNG: O(N) — chỉ cập nhật phần thay đổi
def max_sum_k(arr, k):
    if len(arr) < k:
        return 0
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

❌ Sai lầm 2: Nhầm fixed-size với variable-size

Vấn đề: Dùng cách tiếp cận fixed-size (thử mọi kích thước K) cho bài toán variable-size.

python

# SAI: O(N²) — thử tất cả kích thước window
def smallest_subarray(arr, target):
    for k in range(1, len(arr) + 1):
        for i in range(len(arr) - k + 1):
            if sum(arr[i:i+k]) >= target:
                return k
    return 0

Tại sao sai: Variable-size window không cần thử mọi kích thước. Con trỏ right mở rộng đến khi thỏa điều kiện, rồi left thu hẹp để tối ưu. Mỗi phần tử vào/ra window đúng 1 lần → $O (N)$ .

python

# ĐÚNG: O(N) — expand right, shrink left
def smallest_subarray(arr, target):
    min_len = float('inf')
    window_sum = left = 0
    for right in range(len(arr)):
        window_sum += arr[right]
        while window_sum >= target:
            min_len = min(min_len, right - left + 1)
            window_sum -= arr[left]
            left += 1
    return min_len if min_len != float('inf') else 0

❌ Sai lầm 3: Quên xử lý edge case kích thước mảng

Vấn đề: Không kiểm tra len(arr) < k trước khi tạo window đầu tiên.

python

# SAI: Crash khi k > len(arr)
def max_avg(arr, k):
    window_sum = sum(arr[:k])  # IndexError nếu arr rỗng
    return window_sum / k      # ZeroDivisionError nếu k = 0

Tại sao sai: Trong production, input không bao giờ đáng tin. API nhận k = 0 hoặc mảng rỗng là chuyện thường ngày.

python

# ĐÚNG: Validate input trước khi xử lý
def max_avg(arr, k):
    if not arr or k <= 0 or k > len(arr):
        raise ValueError(f"Invalid: len={len(arr)}, k={k}")
    window_sum = sum(arr[:k])
    max_avg = window_sum / k
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_avg = max(max_avg, window_sum / k)
    return max_avg

❌ Sai lầm 4: Không xóa entry khỏi HashMap khi tần suất về 0

Vấn đề: Trong bài toán sliding window + HashMap, giảm tần suất về 0 nhưng không xóa key.

python

# SAI: len(freq) sai vì key có value = 0 vẫn đếm
freq[s[left]] -= 1
left += 1
# freq = {'a': 0, 'b': 2} → len(freq) = 2 thay vì 1!

Tại sao sai: Điều kiện while len(freq) > k không bao giờ thỏa mãn đúng, window không thu hẹp → kết quả sai.

python

# ĐÚNG: Xóa key khi tần suất về 0
freq[s[left]] -= 1
if freq[s[left]] == 0:
    del freq[s[left]]
left += 1

Under the Hood

Hiệu năng

Biến thể	Time	Space	Ghi chú
Fixed-size window	$O (N)$	$O (1)$	Mỗi phần tử xử lý đúng 1 lần
Variable-size window	$O (N)$	$O (1)$	Mỗi phần tử vào/ra window tối đa 1 lần
Window + HashMap	$O (N)$	$O (K)$	K = số ký tự phân biệt trong window
Sliding window log (rate limit)	$O (N)$ amortized	$O (W)$	W = max request trong window

Tại sao variable-size vẫn O(N)? Dù có vòng while bên trong vòng for, con trỏ left chỉ tăng, không bao giờ quay lại. Tổng số lần left di chuyển trong toàn bộ thuật toán ≤ N. Đây là phân tích amortized — nhìn tổng thể thay vì từng bước.

Nội bộ triển khai

Cache locality: Sliding window trên array liên tục có cache hit rate rất cao vì truy cập tuần tự. Đây là lý do nó nhanh hơn trên thực tế so với phân tích Big O thuần túy — CPU prefetcher dự đoán đúng pattern truy cập.

Branch prediction: Vòng while thu hẹp window thường chạy 0-2 lần mỗi iteration (amortized). CPU branch predictor nhanh chóng "học" pattern này, giảm pipeline stall.

So sánh với deque-based approach: Một số bài toán (sliding window maximum) cần monotonic deque thay vì sum đơn giản. Deque approach vẫn $O (N)$ nhưng constant factor lớn hơn do pointer chasing thay vì array access.

Trade-offs

Khi NÊN dùng	Khi KHÔNG NÊN dùng
Subarray/substring liên tục	Subsequence (không liên tục)
Tổng, trung bình, đếm trong window	Cần sắp xếp/median trong window
Điều kiện monotone (thỏa thì shrink)	Điều kiện phức tạp phi tuyến
Data stream liên tục	Random access pattern

Sliding window không giải được mọi bài toán $O (N^{2})$ . Nó chỉ hiệu quả khi kết quả window mới có thể tính nhanh từ window cũ (cộng/trừ, thêm/xóa HashMap entry). Nếu cần sắp xếp lại window mỗi lần trượt (ví dụ: tìm median), cần cấu trúc dữ liệu bổ sung như balanced BST hoặc two-heap.

Checklist ghi nhớ

✅ Checklist triển khai

Nhận diện bài toán

[ ] Đề bài có từ khóa "contiguous", "subarray", "substring" → nghĩ Sliding Window
[ ] Xác định fixed-size (K cho trước) hay variable-size (tìm min/max length)
[ ] Kiểm tra: kết quả window mới có tính được từ window cũ trong O(1) không?

Triển khai

[ ] Validate input: len(arr) < k, mảng rỗng, k ≤ 0
[ ] Fixed: khởi tạo window đầu tiên rồi mới bắt đầu trượt
[ ] Variable: right mở rộng, left thu hẹp khi điều kiện thỏa
[ ] HashMap: xóa key khi tần suất về 0 — không để "key ma" tồn tại

Production

[ ] Rate limiter: dùng time.monotonic() thay time.time() (tránh clock drift)
[ ] Streaming: recalibrate tổng tích lũy định kỳ (tránh floating-point drift)
[ ] Thread-safety: thêm lock nếu nhiều goroutine/thread cùng truy cập window

Bài tập luyện tập

Bài 1: Trung bình các subarray kích thước K — Foundation

Đề bài: Cho mảng số nguyên và K, trả về mảng trung bình của tất cả subarray liên tiếp kích thước K.

Input: arr = [1, 3, 2, 6, -1, 4, 1, 8, 2], k = 5 Output: [2.2, 2.8, 2.4, 3.6, 2.8]

🧠 Quiz

Câu hỏi kiểm tra: Độ phức tạp thời gian tối ưu cho bài toán này là gì?

[ ] A. O(N × K) — dùng hai vòng for
[ ] B. O(N log N) — dùng sorting
[x] C. O(N) — dùng sliding window
[ ] D. O(K) — chỉ cần duyệt K phần tử Giải thích: Sliding window duyệt mảng một lần duy nhất. Mỗi bước trượt chỉ thực hiện 1 phép trừ + 1 phép cộng + 1 phép chia. Tổng cộng N - K + 1 bước → O(N).

💡 Gợi ý

Tính tổng window đầu tiên bằng sum(arr[:k])
Mỗi bước: window_sum += arr[i] - arr[i-k], rồi chia cho k

✅ Lời giải

python

def find_averages(arr: list[int], k: int) -> list[float]:
    if len(arr) < k:
        return []
    result = []
    window_sum = sum(arr[:k])
    result.append(window_sum / k)
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        result.append(window_sum / k)
    return result

Phân tích: Time O(N), Space O(N-K+1) cho kết quả. Không cần HashMap vì chỉ tính tổng.

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

Đề bài: Cho chuỗi s, tìm độ dài chuỗi con dài nhất không chứa ký tự trùng lặp.

Input: s = "abcabcbb" → Output: 3 (chuỗi "abc") Input: s = "bbbbb" → Output: 1

🧠 Quiz

Câu hỏi kiểm tra: Khi phát hiện ký tự trùng lặp trong window, bước tiếp theo đúng là gì?

[ ] A. Reset window từ đầu chuỗi
[ ] B. Xóa toàn bộ HashMap và bắt đầu lại
[x] C. Thu hẹp left cho đến khi không còn trùng lặp
[ ] D. Bỏ qua ký tự trùng và tiếp tục mở rộng right Giải thích: Thu hẹp left loại bỏ ký tự cũ ra khỏi window cho đến khi ký tự mới thêm vào không còn trùng. Không cần reset từ đầu — đó sẽ là O(N²).

💡 Gợi ý

Dùng HashMap lưu vị trí cuối cùng của mỗi ký tự
Khi gặp ký tự đã có trong window: left = max(left, last_pos[char] + 1)

✅ Lời giải

python

def length_of_longest_substring(s: str) -> int:
    last_pos: dict[str, int] = {}
    max_len = 0
    left = 0

    for right in range(len(s)):
        if s[right] in last_pos and last_pos[s[right]] >= left:
            left = last_pos[s[right]] + 1
        last_pos[s[right]] = right
        max_len = max(max_len, right - left + 1)

    return max_len

Phân tích: Time O(N), Space O(min(N, charset)). Trick: dùng max(left, ...) thay vì xóa HashMap — tránh duyệt lại các ký tự đã bỏ qua.

Bài 3: Tìm tất cả anagram trong chuỗi — Advanced

Đề bài: Cho chuỗi text và pattern, tìm tất cả vị trí bắt đầu của các anagram của pattern trong text.

Input: text = "cbaebabacd", pattern = "abc" → Output: [0, 6]

💡 Gợi ý

Window size cố định = len(pattern)
Dùng hai HashMap: pattern frequency và window frequency
Khi hai HashMap bằng nhau → tìm thấy anagram

✅ Lời giải

python

from collections import Counter

def find_anagrams(text: str, pattern: str) -> list[int]:
    if len(pattern) > len(text):
        return []

    p_count = Counter(pattern)
    w_count = Counter(text[:len(pattern)])
    result = []
    k = len(pattern)

    if w_count == p_count:
        result.append(0)

    for i in range(k, len(text)):
        w_count[text[i]] += 1

        left_char = text[i - k]
        w_count[left_char] -= 1
        if w_count[left_char] == 0:
            del w_count[left_char]

        if w_count == p_count:
            result.append(i - k + 1)

    return result

Phân tích: Time O(N), Space O(K) với K = số ký tự phân biệt trong pattern. So sánh hai Counter là O(K), không phải O(N). Edge case: pattern dài hơn text → trả về mảng rỗng.

Liên kết học tiếp

Từ khóa glossary: sliding window, cửa sổ trượt, two-pointer, variable window, fixed window, subarray, substring, amortized analysis

Tìm kiếm liên quan: kỹ thuật hai con trỏ, tối ưu vòng lặp, bài toán mảng con, chuỗi con dài nhất

Sliding Window — Kỹ thuật cửa sổ trượt ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Fixed-Size Window — Cửa sổ cố định ​

Variable-Size Window — Cửa sổ co giãn ​

Sliding Window + HashMap — Bài toán chuỗi ​

Thực chiến ​

Tình huống: Rate Limiting với Sliding Window Log ​

Tình huống: Streaming Analytics — Moving Average ​

Sai lầm điển hình ​

❌ Sai lầm 1: Dùng brute-force khi có thể slide ​

❌ Sai lầm 2: Nhầm fixed-size với variable-size ​

❌ Sai lầm 3: Quên xử lý edge case kích thước mảng ​

❌ Sai lầm 4: Không xóa entry khỏi HashMap khi tần suất về 0 ​

Under the Hood ​

Hiệu năng ​

Nội bộ triển khai ​

Trade-offs ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Trung bình các subarray kích thước K — Foundation ​

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

Bài 3: Tìm tất cả anagram trong chuỗi — Advanced ​

Liên kết học tiếp ​

Sliding Window — Kỹ thuật cửa sổ trượt

Bức tranh tư duy

Cốt lõi kỹ thuật

Fixed-Size Window — Cửa sổ cố định

Variable-Size Window — Cửa sổ co giãn

Sliding Window + HashMap — Bài toán chuỗi

Thực chiến

Tình huống: Rate Limiting với Sliding Window Log

Tình huống: Streaming Analytics — Moving Average

Sai lầm điển hình

❌ Sai lầm 1: Dùng brute-force khi có thể slide

❌ Sai lầm 2: Nhầm fixed-size với variable-size

❌ Sai lầm 3: Quên xử lý edge case kích thước mảng

❌ Sai lầm 4: Không xóa entry khỏi HashMap khi tần suất về 0

Under the Hood

Hiệu năng

Nội bộ triển khai

Trade-offs

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Trung bình các subarray kích thước K — Foundation

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

Bài 3: Tìm tất cả anagram trong chuỗi — Advanced

Liên kết học tiếp