209 长度最小的子数组

🚀 相关链接

LeetCode 209 - 长度最小的子数组

📜 描述

给定一个含有 n 个正整数的数组和一个正整数 target。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0。

💡 示例

• 输入: target = 7, nums = [2,3,1,2,4,3]
• 输出: 2
• 解释: 子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2

• 输入: target = 4, nums = [1,4,4]
• 输出: 1

示例 3

• 输入: target = 11, nums = [1,1,1,1,1,1,1,1]
• 输出: 0

📝 提示

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4

进阶

如果你已经实现 O(n) 时间复杂度的解法，请尝试设计一个 O(n log(n)) 时间复杂度的解法。

💭 思路

1. 暴力解法：

   • 使用双重循环枚举所有可能的子数组，计算子数组的和，并记录最小的长度。
   • 时间复杂度：O(n^2)，在LeetCode中会超时。

2. 前缀和 + 二分查找：

   • 先计算数组的前缀和数组 sums。
   • 对于每个位置 i，使用二分查找找到第一个满足 sums[j] - sums[i-1] >= target 的 j，并更新最小长度。
   • 时间复杂度：O(n log(n))。

3. 滑动窗口：

   • 维护一个窗口 [start, end]，计算窗口内的和 sum。
   • 如果 sum >= target，更新最小长度，并尝试缩小窗口（start++）。
   • 如果 sum < target，扩大窗口（end++）。
   • 时间复杂度：O(n)。

💻 代码实现

1. 暴力解法（超时）

public int minSubArrayLen(int target, int[] nums) {
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = 1; j <= ans && j + i - 1 < nums.length; j++) {
            sum += nums[i + j - 1];
            if (sum >= target) {
                ans = j;
            }
        }
    }
    return ans == Integer.MAX_VALUE ? 0 : ans;
}

2. 前缀和 + 二分查找

public int minSubArrayLen(int target, int[] nums) {
    int ans = Integer.MAX_VALUE;
    int[] sums = new int[nums.length + 1];
    sums[0] = 0;
    for (int i = 1; i <= nums.length; i++) {
        sums[i] = sums[i - 1] + nums[i - 1];
    }
    for (int i = 1; i <= nums.length; i++) {
        int bound = Arrays.binarySearch(sums, sums[i - 1] + target);
        if (bound < 0) {
            bound = -bound - 1; // Arrays.binarySearch特性
        }
        if (bound <= nums.length) {
            ans = Math.min(ans, bound - (i - 1));
        }
    }
    return ans == Integer.MAX_VALUE ? 0 : ans;
}

3. 滑动窗口

public int lengthOfLongestSubstring(String s) {
        List<Character> list = new ArrayList<>();
        int l = 0, r= 0, ans = 0;
        while(l <= r && r< s.length()){
            if (l == r){
                list.add(s.charAt(l));
                ans = Math.max(ans, list.size());
                r++;
            }else{
                Character c = s.charAt(r);
                if (list.contains(c)){
                    list.removeFirst();
                    l++;
                }else{
                    list.add(s.charAt(r));
                    ans = Math.max(ans, list.size());
                    r++;
                }
            }

        }
        return ans;
    }