2.17 ✅ Cửa sổ trượt (Sliding Window)

- Cách viết kinh điển của cửa sổ trượt (sliding window) với hai con trỏ: con trỏ phải liên tục dịch sang phải đến khi không thể dịch tiếp (điều kiện tuỳ bài). Khi con trỏ phải chạm biên phải, bắt đầu dịch con trỏ trái để “nhả” biên trái của cửa sổ. Các bài: 3, 76, 209, 424, 438, 567, 713, 763, 845, 881, 904, 978, 992, 1004, 1040, 1052.
left, right := 0, -1 for left < len(s) { if right+1 < len(s) && freq[s[right+1]-'a'] == 0 { freq[s[right+1]-'a']++ right++ } else { freq[s[left]-'a']-- left++ } result = max(result, right-left+1) }
- Các bài kinh điển của cửa sổ trượt: 239, 480.
| STT | Tiêu đề | Lời giải | Độ khó | Độ phức tạp thời gian | Độ phức tạp bộ nhớ | Yêu thích | Tỷ lệ AC (Acceptance) |
|---|---|---|---|---|---|---|---|
| 0003 | Chuỗi con dài nhất không lặp ký tự (Longest Substring Without Repeating Characters) | Go | Medium | O(n) | O(1) | ❤️ | 33.8% |
| 0030 | Chuỗi con là phép nối tất cả các từ (Substring with Concatenation of All Words) | Go | Hard | 31.2% | |||
| 0076 | Chuỗi con cửa sổ nhỏ nhất (Minimum Window Substring) | Go | Hard | O(n) | O(n) | ❤️ | 40.9% |
| 0187 | Các chuỗi DNA lặp lại (Repeated DNA Sequences) | Go | Medium | 47.0% | |||
| 0209 | Tổng mảng con tối thiểu đạt ngưỡng (Minimum Size Subarray Sum) | Go | Medium | 45.0% | |||
| 0219 | Có phần tử trùng II (Contains Duplicate II) | Go | Easy | 42.6% | |||
| 0220 | Có phần tử trùng III (Contains Duplicate III) | Go | Hard | 22.1% | |||
| 0239 | Giá trị lớn nhất của cửa sổ trượt (Sliding Window Maximum) | Go | Hard | O(n * k) | O(n) | ❤️ | 46.3% |
| 0395 | Chuỗi con dài nhất có ít nhất K ký tự lặp lại (Longest Substring with At Least K Repeating Characters) | Go | Medium | 44.8% | |||
| 0424 | Thay thế để có chuỗi lặp lại dài nhất (Longest Repeating Character Replacement) | Go | Medium | O(n) | O(1) | 52.0% | |
| 0438 | Tìm tất cả anagram trong chuỗi (Find All Anagrams in a String) | Go | Medium | 50.2% | |||
| 0480 | Trung vị cửa sổ trượt (Sliding Window Median) | Go | Hard | O(n * log k) | O(k) | ❤️ | 41.1% |
| 0567 | Hoán vị trong chuỗi (Permutation in String) | Go | Medium | O(n) | O(1) | ❤️ | 44.3% |
| 0632 | Khoảng nhỏ nhất bao phủ phần tử từ K danh sách (Smallest Range Covering Elements from K Lists) | Go | Hard | 61.0% | |||
| 0643 | Trung bình lớn nhất của mảng con I (Maximum Average Subarray I) | Go | Easy | 43.7% | |||
| 0658 | Tìm K phần tử gần nhất (Find K Closest Elements) | Go | Medium | 46.8% | |||
| 0713 | Tích mảng con nhỏ hơn K (Subarray Product Less Than K) | Go | Medium | 45.8% | |||
| 0718 | Độ dài tối đa của mảng con lặp lại (Maximum Length of Repeated Subarray) | Go | Medium | 51.3% | |||
| 0862 | Mảng con ngắn nhất có tổng ít nhất K (Shortest Subarray with Sum at Least K) | Go | Hard | 26.0% | |||
| 0904 | Trái cây vào giỏ (Fruit Into Baskets) | Go | Medium | 43.7% | |||
| 0930 | Mảng con nhị phân có tổng (Binary Subarrays With Sum) | Go | Medium | 52.2% | |||
| 0978 | Mảng con biến động dài nhất (Longest Turbulent Subarray) | Go | Medium | O(n) | O(1) | ❤️ | 47.2% |
| 0992 | Mảng con có K số nguyên khác nhau (Subarrays with K Different Integers) | Go | Hard | O(n) | O(n) | ❤️ | 54.6% |
| 0995 | Số lần lật bit liên tiếp K tối thiểu (Minimum Number of K Consecutive Bit Flips) | Go | Hard | O(n) | O(1) | ❤️ | 51.2% |
| 1004 | Số 1 liên tiếp tối đa III (Max Consecutive Ones III) | Go | Medium | O(n) | O(1) | 63.2% | |
| 1052 | Chủ tiệm sách khó chịu (Grumpy Bookstore Owner) | Go | Medium | O(n log n) | O(1) | 57.1% | |
| 1208 | Lấy các chuỗi con bằng nhau trong ngân sách (Get Equal Substrings Within Budget) | Go | Medium | 48.6% | |||
| 1234 | Thay chuỗi con để chuỗi cân bằng (Replace the Substring for Balanced String) | Go | Medium | 37.2% | |||
| 1423 | Điểm tối đa có thể lấy từ các lá bài (Maximum Points You Can Obtain from Cards) | Go | Medium | 52.2% | |||
| 1438 | Mảng con liên tục dài nhất có chênh lệch tuyệt đối không vượt quá giới hạn (Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit) | Go | Medium | 48.3% | |||
| 1658 | Số thao tác tối thiểu để giảm X về 0 (Minimum Operations to Reduce X to Zero) | Go | Medium | 37.6% | |||
| 1695 | Giá trị xóa tối đa (Maximum Erasure Value) | Go | Medium | 57.6% | |||
| 1696 | Trò chơi nhảy VI (Jump Game VI) | Go | Medium | 46.1% | |||
| 1763 | Chuỗi con "nice" dài nhất (Longest Nice Substring) | Go | Easy | 61.5% | |||
| 1984 | Chênh lệch nhỏ nhất giữa điểm cao nhất và thấp nhất của K điểm (Minimum Difference Between Highest and Lowest of K Scores) | Go | Easy | 54.5% | |||
| ------------ | ------------------------------------------------------- | ------- | ---------------- | --------------- | ------------- | ------------- | ------------- |