题目描述

和大于等于target 的最短子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsL, numsL+1, …, numsR-1, numsR] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1:

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

示例 2:

  1. 输入：target = 4, nums = [1,4,4]
  2. 输出：1

示例 3:

  1. 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
  2. 输出：0

提示：

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

    解题思路

    滑动窗口，从头开始顺序遍历，以i为基准，顺序求满足要求的最小要求。

    实现代码

    1. public int minSubArrayLen(int target, int[] nums) {
    2. int n = nums.length;
    3. if (n == 0) {
    4.   return 0;
    5. }
    6. int ans = Integer.MAX_VALUE;
    7. int start = 0, end = 0;
    8. int sum = 0;
    9. while (end < n) {
    10.   sum += nums[end];
    11.   while (sum >= target) {
    12.     ans = Math.min(ans, end - start + 1);
    13.     sum -= nums[start];
    14.     start++;
    15.   }
    16.   end++;
    17. }
    18. return ans == Integer.MAX_VALUE ? 0 : ans;
    19. }

    时间及空间复杂度分析

    时间复杂度，O(n)
    image.png

    拓展思路

    前缀和 + 二分查找
    image.png