Cho một mảng số nguyên dương có độ dài n và một giá trị ngưỡng nguyên dương target. Tìm độ dài mảng con liên tiếp nhỏ nhất có tổng các phần tử lớn hơn hoặc bằng target. Trả về 0 nếu không tồn tại.

Ví dụ 1:

Đầu vào: target = 7, nums = [2,3,1,2,4,3]
Đầu ra: 2
Giải thích: Mảng con [4,3] thỏa mãn và có độ dài nhỏ nhất.

Ví dụ 2:

Đầu vào: target = 4, nums = [1,4,4]
Đầu ra: 1

Ví dụ 3:

Đầu vào: target = 11, nums = [1,1,1,1,1,1,1,1]
Đầu ra: 0

Phương Pháp Cửa Sổ Trượt

Với điều kiện mảng chỉ chứa số nguyên dương, một giải pháp tối ưu là sử dụng kỹ thuật cửa sổ trượt. Ý tưởng là duy trì một khoảng con liên tiếp (cửa sổ) có tổng được điều chỉnh động bằng cách di chuyển hai biên.

• Khi tổng hiện tại nhỏ hơn target, mở rộng cửa sổ về bên phải để tăng tổng.
• Khi tổng hiện tại lớn hơn hoặc bằng target, ghi nhận độ dài cửa sổ và thu hẹp nó từ bên trái để tìm cửa sổ nhỏ hơn có thể vẫn thỏa mãn.

Độ phức tạp thời gian là O(n) và không gian là O(1).

class Solution {
    public int minSubArrayLen(int target, int[] arr) {
        int minLength = Integer.MAX_VALUE;
        int currentSum = 0;
        int left = 0;

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

            while (currentSum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                currentSum -= arr[left];
                left++;
            }
        }

        return minLength == Integer.MAX_VALUE ?, 0 : minLength;
    }
}

Cách Triển Khai Với Hai Biến Chỉ Số Rõ Ràng

Một biến thể khác của kỹ thuật trên là quản lý rõ ràng hai biên của cửa sổ và điều kiện di chuyển của chúng.

public class SubarrayMinLength {
    public int findMinLength(int threshold, int[] numbers) {
        int start = 0;
        int end = -1;
        int windowSum = 0;
        int bestLength = numbers.length + 1;

        while (start < numbers.length) {
            if (end + 1 < numbers.length && windowSum < threshold) {
                end++;
                windowSum += numbers[end];
            } else {
                windowSum -= numbers[start];
                start++;
            }

            if (windowSum >= threshold) {
                bestLength = Math.min(bestLength, end - start + 1);
            }
        }

        return bestLength == numbers.length + 1 ? 0 : bestLength;
    }
}

Cả hai cách tiếp cận đều dựa trên nguyên lý cửa sổ trượt, tận dụng tính chất số dương để đảm bảo tổng tăng khi mở rộng và giảm khi thu hẹp.