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.
STTTiêu đềLời giảiĐộ khóĐộ phức tạp thời gianĐộ phức tạp bộ nhớYêu thíchTỷ lệ AC (Acceptance)
0003Chuỗi con dài nhất không lặp ký tự (Longest Substring Without Repeating Characters)GoMediumO(n)O(1)❤️33.8%
0030Chuỗi con là phép nối tất cả các từ (Substring with Concatenation of All Words)GoHard31.2%
0076Chuỗi con cửa sổ nhỏ nhất (Minimum Window Substring)GoHardO(n)O(n)❤️40.9%
0187Các chuỗi DNA lặp lại (Repeated DNA Sequences)GoMedium47.0%
0209Tổng mảng con tối thiểu đạt ngưỡng (Minimum Size Subarray Sum)GoMedium45.0%
0219Có phần tử trùng II (Contains Duplicate II)GoEasy42.6%
0220Có phần tử trùng III (Contains Duplicate III)GoHard22.1%
0239Giá trị lớn nhất của cửa sổ trượt (Sliding Window Maximum)GoHardO(n * k)O(n)❤️46.3%
0395Chuỗ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)GoMedium44.8%
0424Thay thế để có chuỗi lặp lại dài nhất (Longest Repeating Character Replacement)GoMediumO(n)O(1)52.0%
0438Tìm tất cả anagram trong chuỗi (Find All Anagrams in a String)GoMedium50.2%
0480Trung vị cửa sổ trượt (Sliding Window Median)GoHardO(n * log k)O(k)❤️41.1%
0567Hoán vị trong chuỗi (Permutation in String)GoMediumO(n)O(1)❤️44.3%
0632Khoảng nhỏ nhất bao phủ phần tử từ K danh sách (Smallest Range Covering Elements from K Lists)GoHard61.0%
0643Trung bình lớn nhất của mảng con I (Maximum Average Subarray I)GoEasy43.7%
0658Tìm K phần tử gần nhất (Find K Closest Elements)GoMedium46.8%
0713Tích mảng con nhỏ hơn K (Subarray Product Less Than K)GoMedium45.8%
0718Độ dài tối đa của mảng con lặp lại (Maximum Length of Repeated Subarray)GoMedium51.3%
0862Mảng con ngắn nhất có tổng ít nhất K (Shortest Subarray with Sum at Least K)GoHard26.0%
0904Trái cây vào giỏ (Fruit Into Baskets)GoMedium43.7%
0930Mảng con nhị phân có tổng (Binary Subarrays With Sum)GoMedium52.2%
0978Mảng con biến động dài nhất (Longest Turbulent Subarray)GoMediumO(n)O(1)❤️47.2%
0992Mảng con có K số nguyên khác nhau (Subarrays with K Different Integers)GoHardO(n)O(n)❤️54.6%
0995Số lần lật bit liên tiếp K tối thiểu (Minimum Number of K Consecutive Bit Flips)GoHardO(n)O(1)❤️51.2%
1004Số 1 liên tiếp tối đa III (Max Consecutive Ones III)GoMediumO(n)O(1)63.2%
1052Chủ tiệm sách khó chịu (Grumpy Bookstore Owner)GoMediumO(n log n)O(1)57.1%
1208Lấy các chuỗi con bằng nhau trong ngân sách (Get Equal Substrings Within Budget)GoMedium48.6%
1234Thay chuỗi con để chuỗi cân bằng (Replace the Substring for Balanced String)GoMedium37.2%
1423Điểm tối đa có thể lấy từ các lá bài (Maximum Points You Can Obtain from Cards)GoMedium52.2%
1438Mả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)GoMedium48.3%
1658Số thao tác tối thiểu để giảm X về 0 (Minimum Operations to Reduce X to Zero)GoMedium37.6%
1695Giá trị xóa tối đa (Maximum Erasure Value)GoMedium57.6%
1696Trò chơi nhảy VI (Jump Game VI)GoMedium46.1%
1763Chuỗi con "nice" dài nhất (Longest Nice Substring)GoEasy61.5%
1984Chê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)GoEasy54.5%
------------------------------------------------------------------------------------------------------------------------------------------------