长度最小的子数组

约 1244 字大约 4 分钟

2025-02-25

209. 长度最小的子数组

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

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

示例 1：

输入：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 <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

进阶：

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

我们只需要找到 sums[k]-sums[j]>=s，那么 k-j 就是满足的连续子数组，但不一定是最小的，所以我们要继续找，直到找到最小的为止。怎么找呢，我们可以使用两个 for 循环来枚举，但这和暴力求解一样了，所以我们可以换种思路，要求 sums[k]-sums[j]>=s 我们可以求满足 sums[j]+s<=sums[k] 的最短的 k-j。数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性。

因为问题要求的是连续子数组，排序会破坏数组的顺序。

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length; // 获取数组长度
        if (n == 0) { // 如果数组为空，直接返回0
            return 0;
        }

        int ans = Integer.MAX_VALUE; // 初始化最小子数组长度为无穷大
        int[] sums = new int[n + 1]; // 创建前缀和数组，长度为 n+1

        // 为了方便计算，令 size = n + 1
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1]; // 计算前缀和
        }

        // 遍历每个前缀和
        for (int i = 0; i <= n; i++) {// 其实i不用遍历n，因为s+sums[n]一定大于sums[n]，所以bound一定是-n-1，从而bound=n，所以bound-i=n-n一定是0
            int target = s + sums[i]; // 计算目标前缀和，注意是sums[i]不是nums[i]！
            // 二分查找未找到目标值时会返回“-插入点-1”，之所以是-1是因为要避免插入点为0时的歧义，因为我们要用正负来区分是否找到目标值。重点！
            int bound = Arrays.binarySearch(sums, target); // 二分查找目标前缀和的位置
            if (bound < 0) {
                bound = -bound - 1; // 如果未找到，返回插入点，即第一个大于目标值的元素的位置。
            }
            if (bound <= n) { // 检查插入点是否在有效范围内
                ans = Math.min(ans, bound - i); // 更新最小子数组长度，[i+1, bound]的长度
            }
        }

        return ans == Integer.MAX_VALUE ? 0 : ans; // 如果没有找到符合条件的子数组，返回0；否则返回最小子数组长度
    }
}

时间复杂度: $O(n \log n)$ ，其中 $n$ 是数组的长度。需要遍历每个下标作为子数组的开始下标，遍历的时间复杂度是 $O(n)$ ，对于每个开始下标，需要通过二分查找得到长度最小的子数组，二分查找得时间复杂度是 $O(\log n)$ ，因此总时间复杂度是 $O(n \log n)$ 。
空间复杂度： $O(n)$ ，其中 $n$ 是数组的长度。额外创建数组 sums 存储前缀和。

滑动窗口

穷举，一个变量维护窗口内元素之和，当窗口和大于等于目标和时要缩小左边界，每缩小一次，就要更新一次最小长度和窗口和。

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0, right = 0;
        // 维护窗口内元素之和
        int windowSum = 0;
        int res = Integer.MAX_VALUE;

        while (right < nums.length) {
            // 扩大窗口
            windowSum += nums[right];
            right++;
            
            // 改成left<=right也可以，但是没必要。为什么需要left<right？因为自增后的right对应的值不在窗口中，
            // 所以left不能走到right，即最多删除[left, right-1]的数。
            // 其实left<right也没必要。因为题目说nums中每个数都是正数，所以只要左边界收缩，windowSum一定减小，而s是大于0的，所以left最多走到right。
            while (windowSum >= s && left < right) {
                // 已经达到 target，缩小窗口，同时更新答案
                res = Math.min(res, right - left);
                // 为什么要缩小窗口？因为以后面的数为起点的话，有可能找到更好的答案。
                windowSum -= nums[left];
                left++;
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

时间复杂度： $O(n)$ ，其中 $n$ 是数组的长度。指针 start 和 end 最多各移动 $n$ 次。
空间复杂度： $O(1)$ 。

长度最小的子数组

209. 长度最小的子数组

前缀和+二分

滑动窗口