Top những kĩ thuật lập trình mà trường học không dạy bạn - #1 Sliding window

Sliding window là gì?

đã bao giờ các bạn gặp 1 bài toán kiểu như tìm độ dài, min/max của của chuỗi con có độ dài X thỏa mãn N điều kiện không? , hẳn là những bài toán như vậy các bạn đã gặp khá nhiều thời còn đi học và các giải quyết duy nhất là sử dụng vòng lặp lồng như ví dụ dưới đây

Tìm dãy con nhỏ nhất có tổng lớn hơn hoặc bằng S
arr = {2, 3, 1, 2, 4, 3};
S = 7
output: result = 2, ta có độ dài của mảng con nhỏ nhất lớn hơn S=7 là {4,3}

brute force solutions:

public static int minSubArrayLen(int S, int[] arr) {
        int n = arr.length;
        int minLength = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += arr[j];
                if (sum >= S) {
                    minLength = Math.min(minLength, j - i + 1);
                    break; 
                }
            }
        }
        return (minLength == Integer.MAX_VALUE) ? 0 : minLength;
    }

Như các bạn có thể thấy độ phức tạp của cách làm trên là O(n2), việc này làm bài toán của chúng ta sẽ đặc biệt chậm nếu kích thước mảng quá lớn, hôm nay tôi xin giới thiệu cho các bạn 1 kĩ thuật nhằm làm giảm độ phức tạp về mức O(n) đó là kĩ thuật silding window

Ý tưởng chính

Thay vì tính toán lại toàn bộ dữ liệu sau mỗi bước, ta có thể tạo ra 1 biến thay đổi sau mỗi điều kiện nhất định hoặc mỗi lần lặp, đây chính là cửa sổ của chúng ta, Điều này giúp giảm độ phức tạp về thời gian từ O(n²) xuống O(n) trong nhiều bài toán

Phân loại cụ thể sliding window

1. Fixed-size Sliding Window

đây là dạng kĩ thuật dùng cửa sổ có kích thước cố định K được trượt qua một chuỗi hoặc mảng để tính toán hoặc tìm kiếm các giá trị mong muốn một cách hiệu quả.

• Sử dụng hai con trỏ: Một con trỏ đầu cửa sổ (left) và một con trỏ cuối cửa sổ (right).
• Duy trì một cửa sổ có kích thước cố định kk và cập nhật dữ liệu khi cửa sổ trượt sang phải.
• Thay vì tính toán lại toàn bộ mỗi lần cửa sổ di chuyển, ta chỉ cập nhật phần tử mới thêm vào và loại bỏ phần tử cũ ra khỏi cửa sổ.

vd: Cho một mảng số nguyên nums và một số nguyên k, hãy tìm giá trị trung bình lớn nhất của một mảng con có độ dài k.

=> đặc điểm nhận dạng: - yêu cầu tìm mảng con => có thể áp dụng sliding window - yêu cầu có độ dài k => window không đổi => có thể fixed size

 public double findMaxAverage(int[] nums, int k) {
       // Tính tổng của k phần tử đầu tiên
       int currentSum = 0;
       for (int i = 0; i < k; i++) {
           currentSum += nums[i];
       }
       int maxSum = currentSum;
       for (int i = k; i < nums.length; i++) {
           currentSum += nums[i] - nums[i - k]; // Thêm nums[i], loại bỏ nums[i - k]
           maxSum = Math.max(maxSum, currentSum);
       }

       return (double) maxSum / k; 
   }

2. Dynamic-size Sliding Window

Khác với window ở dạng fixed, kích thước cửa sổ có thể thay đổi trong quá trình duyệt qua mảng hoặc chuỗi. Không giống như Fixed-size Sliding Window, cửa sổ động có thể mở rộng hoặc thu hẹp dựa trên điều kiện bài toán.

Sử dụng hai con trỏ:

right: Dùng để mở rộng cửa sổ (tăng dần).
left: Dùng để thu hẹp cửa sổ khi cần thiết.

Mở rộng cửa sổ: Khi cửa sổ chưa đạt điều kiện mong muốn. Thu hẹp cửa sổ: Khi cửa sổ vi phạm điều kiện hoặc cần tối ưu hơn.

vd: Giả sử có một mảng arr = [4, 2, 7, 1, 9, 3], và bài toán yêu cầu tìm độ dài dãy con có tổng nhỏ nhất lớn hơn hoặc bằng S=15

public static int slidingWindowDynamicSize(int [] arr, int targetNumber) {
        int minLength = Integer.MAX_VALUE;
        int L = 0, R = 0, sum = 0;
        for (;R < arr.length; R++) {
            sum += arr[R];
            while (sum >= 15) {
                minLength = Math.min(minLength, R - L + 1);
                sum -= arr[L];
                L++;
            }
        }
        return minLength;
    }

Một vài dạng mẫu mà các bạn có thể áp dụng ngay trên leetcode

1. Tìm tổng lớn nhất / nhỏ nhất của một dãy con có độ dài cố định

• Dạng bài: Tìm dãy con có tổng lớn nhất trong một mảng.
• Leetcode 53. Maximum Subarray

2. Tìm số lượng dãy con có tổng nhỏ hơn giá trị cho trước

• Dạng bài: Đếm số lượng dãy con có tổng nhỏ hơn một giá trị cố định.
• Bài LeetCode: 713. Subarray Product Less Than K

3. Tìm số lượng chuỗi con thỏa mãn điều kiện về số lượng chữ cái khác nhau

• Dạng bài: Tìm số lượng chuỗi con chứa không quá K ký tự khác nhau.
• Bài LeetCode: 395. Longest Substring with At Least K Repeating Characters

Tóm tắt

Nói chung sliding window là một kỹ thuật tối ưu hóa giúp giảm độ phức tạp thời gian trong các bài toán yêu cầu xử lý trên một dãy số hoặc chuỗi liên tục nó giúp tối ưu hóa việc kiểm tra dãy con, giúp giảm độ phức tạp từ O(N²) xuống O(N), hiện tại còn rất nhiều kĩ thuật khác nữa mà bạn cần phải biết để có thể xử lí các bài leetcode hiệu quả, hãy theo dõi tôi để có thể cập nhật được những kĩ thuật mới nhất