题目: 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s, 找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。

示例: 

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

进阶:

如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(nlogn) 时间复杂度的解法。

解题

思路: 滑动列表。时间复杂度为 O(n), 空间复杂度为 1

  1. 取滑动列表 [left, right];
  2. 若列表 [left, right] 中的取值之和小于 s, 则列表的有边界 right 往右扩张。
  3. 若列表 [left, right] 中的取值之和大于 s, 则列表的左边界 left 往右扩张。
/**
* @param {number} s
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function(s, nums) {
let left = 0, right = -1 // [left, right], 左闭右闭
let minDistance = nums.length + 1 // 存储 left 与 right 间的距离
let sum = 0 // [left, right] 间值的总和
while (left < nums.length - 1) {
if (right < nums.length - 1 && sum < s) {
right++
sum = sum + nums[right]
} else {
sum = sum - nums[left]
left++
}
if (sum >= s) {
minDistance = Math.min(minDistance, right - left + 1)
}
}
if (minDistance === nums.length + 1) return 0
return minDistance
}

Sister Title

3、76、209、438