关于算法:LeetCodeGolang-209-长度最小的子数组

7次阅读

共计 1570 个字符，预计需要花费 4 分钟才能阅读完成。

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

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

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

滑动窗口 能够很好的解决。先贴代码（Go）:

func minSubArrayLen(target int, nums []int) int {l, r, n, minValue := 0, 0, len(nums), math.MaxInt32 //[i,r]
   sum := 0
   for r < n && l <= r {sum += nums[r]
      for sum >= target {minValue = min(minValue, r-l+1)
         sum -= nums[l]
         l++
      }
      r++
   }

   if minValue == math.MaxInt32 {return 0}
   return minValue
}

func min(a int, b int) int {
   if a < b {return a}
   return b
}

核心思想是：

右移 r 时，子数组和变大，因而和不够时，右移 r。
右移 l 时，子数组长度变小，因而和足够时，左移 l。
当右移 r 使得子数组和满足条件时，立即寻找符合条件的最右的 l 并记录。
当右移 l 使得子数组和不满足条件时，立即寻找符合条件的最左的 r 并记录。

在不满足时优先满足条件，在满足条件时优先降低消耗（子数组长度），堪称是 贪婪算法。

比暴力求解少遍历很多状况，例如：(n 为适合的正整数)

当咱们晓得 [l,r] 满足条件时，[l,r+n] 范畴内的子数组不再思考，因为它肯定也满足条件然而比 [l,r] 更长。
当咱们晓得 [l,r] 不满足条件时，[l+n,r] 范畴内的子数组不再思考。因为它肯定也不满足条件。

复杂度剖析：

工夫复杂度：O(n)，其中 n 是数组的长度。指针 l 和 r 最多各挪动 n 次。
空间复杂度：O(1)。

题目在进阶中，有个奇怪的要求：如果你曾经实现 O(n) 工夫复杂度的解法, 请尝试设计一个 O(n log(n)) 工夫复杂度的解法。

好！很有精力！

其实就是为了锤炼下 前缀和 的办法，先贴代码（Go）：

func minSubArrayLen(s int, nums []int) int {n := len(nums)
   if n == 0 {return 0}
   ans := math.MaxInt32
   sums := make([]int, n+1)
   // 为了不便计算，令 size = n + 1
   // sums[0] = 0 意味着前 0 个元素的前缀和为 0
   // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
   // 以此类推
   for i := 1; i <= n; i++ {sums[i] = sums[i-1] + nums[i-1]
   }
   for i := 0; i <= n; i++ {target := s + sums[i]
      bound := sort.SearchInts(sums, target)
      if bound <= n {ans = min(ans, bound-(i))
      }
   }
   if ans == math.MaxInt32 {return 0}
   return ans
}
func min(a int, b int) int {
   if a < b {return a}
   return b
}

每个 sums 元素应用一次 二分搜寻，胜利将复杂度升到了 O(nlogn)。

至于 前缀和 的办法，Emmmmmmmm，当前再说，题目的奇怪要求，在这里应用，不合我意。

复杂度剖析：

工夫复杂度：O(nlogn)，其中 n 是数组的长度。须要遍历每个下标作为子数组的开始下标，遍历的工夫复杂度是 O(n)，对于每个开始下标，须要通过二分查找失去长度最小的子数组，二分查找得工夫复杂度是 O(logn)，因而总工夫复杂度是 O(nlogn)。

空间复杂度：O(n)，其中 n 是数组的长度。额定创立数组 sums 存储前缀和。

正文完