209.长度最小的子数组

题目: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 <= 10^5
1 <= nums[i] <= 10^5

• 进阶：

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

思路

当解决找出数组中满足其总和大于等于目标值 target 的最小子数组长度时，可以采用滑动窗口（双指针）的方法来实现。

1. 初始化指针和变量：

   • 使用两个指针 left 和 right，分别表示滑动窗口的左右边界，初始时都指向数组的起始位置。
   • 使用变量 sum 记录当前窗口内元素的和。
   • 使用变量 minLen 记录找到的满足条件的最小子数组的长度，初始值设为Integer.MAX_VALUE。

2. 移动右指针扩展窗口：

   • 不断将右指针 right 向右移动，同时将当前指向的元素值加到 sum 中。
   • 如果 sum 大于等于 target，则进入缩小窗口的步骤。

3. 缩小窗口：

   • 在 sum 大于等于 target 的情况下，尝试缩小窗口以找到更小的满足条件的子数组。
   • 计算当前窗口的长度 currentLen，更新 minLen 为当前 minLen 和 currentLen 中的较小值。
   • 移动左指针 left，将当前左指针指向的元素值从 sum 中减去，直到 sum 小于 target。

4. 重复直到遍历完数组：

   • 不断移动右指针 right 扩展窗口，然后在满足条件时尝试缩小窗口，直到右指针到达数组末尾。

5. 返回结果：

   • 如果找到了符合条件的子数组，返回 minLen，即为满足条件的最小子数组的长度。
   • 如果没有找到符合条件的子数组，返回 0。

• 时间复杂度:O(n)
• 空间复杂度:O(1)

代码

public int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int right = 0;
    int sum = 0;
    int minLen = Integer.MAX_VALUE;
    // 遍历数组，移动右指针
    while (right < nums.length) {
        // 增加右边界，扩展窗口
        sum += nums[right];
        while (sum >= target) {
            // 计算当前窗口的长度
            int currentLen = right - left + 1;
            // 更新最小长度
            if (currentLen < minLen) {
                minLen = currentLen;
            }
            // 缩小窗口，移动左边界
            sum -= nums[left];
            left++;
        }
        right++;
    }
    // 如果找到了符合条件的子数组，返回最小长度；否则返回 0
    return minLen != Integer.MAX_VALUE ? minLen : 0;
}

思路2

要设计一个 O(n log(n)) 时间复杂度的解法来找出数组中满足其总和大于等于目标值 target 的最小子数组长度，可以结合前缀和数组和二分查找的思想。

1. 前缀和数组：

   • 首先构建一个前缀和数组 prefixSum，其中 prefixSum[i] 表示数组 nums 的前 i 个元素的和。
   • 使用变量 minLen 记录找到的满足条件的最小子数组的长度，初始值设为Integer.MAX_VALUE。

2. 遍历并二分查找：

   • 遍历数组 nums，对于每个结束位置 i，计算当前的前缀和 currentSum = prefixSum[i + 1]。
   • 在之前的前缀和中寻找第一个开始位置 mid，使得 currentSum - prefixSum[mid] >= target。
   • 使用二分查找在前缀和数组中寻找满足条件的 mid。

3. 更新最小长度：

   • 如果找到满足条件的 mid，更新最小长度为 i - mid + 1。

4. 返回结果：

   • 如果找到了符合条件的子数组，返回最小长度；否则返回 0。

• 时间复杂度:O(nlog₂n)
• 空间复杂度:O(n)

代码

public int minSubArrayLen(int target, int[] nums) {
    int[] prefixSum = new int[nums.length + 1];
    int minLen = Integer.MAX_VALUE;
    for (int i = 1; i <= nums.length; i++) {
        prefixSum[i] = nums[i - 1] + prefixSum[i - 1];
    }
    for (int i = 0; i < nums.length; i++) {
        // 计算当前前缀和
        int currentSum = prefixSum[i + 1];
        // 在前缀和数组中二分查找符合条件的起始位置
        int left = 0;
        int right = i;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (currentSum - prefixSum[mid] >= target) {
                minLen = Math.min(minLen, i - mid + 1);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    // 如果找到了符合条件的子数组，返回最小长度；否则返回 0
    return minLen != Integer.MAX_VALUE ? minLen : 0;
}