题目

给定一个含有 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)) 时间复杂度的解法。

注意：本题与主站 209 题相同

解题思路分析

1、暴力法；时间复杂度O(n^2)，空间复杂度O(1)

func minSubArrayLen(target int, nums []int) int {
   res := math.MaxInt32
   for i := 0; i < len(nums); i++ {
      sum := 0
      for j := i; j < len(nums); j++ {
         sum = sum + nums[j]
         if sum >= target {
            if res > j-i+1 {
               res = j - i + 1
            }
            break
         }
      }
   }
   if res == math.MaxInt32 {
      return 0
   }
   return res
}

2、前缀和+二分查找；时间复杂度O(nlog(n))，空间复杂度O(n)

func minSubArrayLen(target int, nums []int) int {
   res := math.MaxInt32
   arr := make([]int, len(nums)+1)
   for i := 1; i <= len(nums); i++ {
      arr[i] = arr[i-1] + nums[i-1]
   }
   for i := 1; i <= len(nums); i++ {
      target := target + arr[i-1]
      index := sort.SearchInts(arr, target)
      if index <= len(nums) {
         if res > index-i+1 {
            res = index - i + 1
         }
      }
   }
   if res == math.MaxInt32 {
      return 0
   }
   return res
}

3、双指针；时间复杂度O(n)，空间复杂度O(1)

func minSubArrayLen(s int, nums []int) int {
   res := math.MaxInt32
   i, j := 0, 0
   sum := 0
   for ; j < len(nums); j++ {
      sum = sum + nums[j]
      for sum >= s {
         if res > j-i+1 {
            res = j - i + 1
         }
         sum = sum - nums[i]
         i++
      }
   }
   if res == math.MaxInt32 {
      return 0
   }
   return res
}

总结

Medium题目，题目同leetcode 209.长度最小的子数组