1. Giới Thiệu Về Sliding Window
Sliding Window là một kỹ thuật tối ưu hóa thuật toán, thường được sử dụng để giảm độ phức tạp của các bài toán liên quan đến xử lý mảng hoặc chuỗi. Thay vì sử dụng hai vòng lặp lồng nhau để duyệt tất cả các trường hợp có thể, kỹ thuật Sliding Window giúp ta tận dụng thông tin từ lần duyệt trước để tính toán hiệu quả hơn.
2. Khi Nào Dùng Sliding Window?
Kỹ thuật này thường được áp dụng khi bài toán yêu cầu:
- Tìm tổng, trung bình, hoặc một tính chất nào đó của một dãy con liên tiếp trong mảng/chuỗi.
- Xác định độ dài tối đa/tối thiểu của một dãy con thỏa mãn điều kiện nào đó.
- Tối ưu hóa các bài toán có cách giải brute-force (O(n^2)) xuống (O(n)).
3. Các Loại Sliding Window
a) Fixed Window (Cửa sổ cố định)
Đây là dạng cơ bản nhất, khi cửa sổ có kích thước cố định k. Ví dụ: Tìm tổng lớn nhất của một dãy con có độ dài k trong mảng.
Ví dụ: Tìm tổng lớn nhất của một dãy con có độ dài k
public int MaxSumSubarray(int[] nums, int k) { int maxSum = 0, windowSum = 0; for (int i = 0; i < k; i++) { windowSum += nums[i]; } maxSum = windowSum; for (int i = k; i < nums.Length; i++) { windowSum += nums[i] - nums[i - k]; maxSum = Math.Max(maxSum, windowSum); } return maxSum;
}
Độ phức tạp: O(n)
b) Dynamic Window (Cửa sổ động)
Dạng này cửa sổ có kích thước thay đổi, thường được sử dụng khi cần tìm dãy con ngắn nhất/dài nhất thỏa mãn một điều kiện nào đó.
Ví dụ: Tìm dãy con ngắn nhất có tổng >= target.
public int MinSubArrayLen(int target, int[] nums) { int left = 0, sum = 0, minLength = int.MaxValue; for (int right = 0; right < nums.Length; right++) { sum += nums[right]; while (sum >= target) { minLength = Math.Min(minLength, right - left + 1); sum -= nums[left]; left++; } } return minLength == int.MaxValue ? 0 : minLength;
}
Độ phức tạp: O(n)
4. Khi Nào Không Nên Dùng Sliding Window?
- Khi phần tử không được sắp xếp và yêu cầu truy cập ngẫu nhiên.
- Khi bài toán yêu cầu kiểm tra nhiều tổ hợp không liên tiếp.
- Khi không có một quy tắc cụ thể nào để mở rộng hoặc thu hẹp cửa sổ.
5. Kết Luận
Kỹ thuật Sliding Window giúp tối ưu hóa đáng kể các bài toán liên quan đến mảng và chuỗi, giảm độ phức tạp từ O(n^2) xuống O(n). Việc hiểu và áp dụng đúng kỹ thuật này sẽ giúp software engineer tối ưu hóa hiệu suất chương trình một cách đáng kể.
Bạn đã từng sử dụng Sliding Window trong bài toán nào chưa? Chia sẻ kinh nghiệm của bạn nhé!