1. 题目描述
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
示例:
输入:s = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
进阶:如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
2. 实现思路
可以使用双指针来解决这个问题:
- 初始化left、right两个指针,初始值为0
- 移动右指针right,并将每一次移动到的右指针指向的值加入到sum中
- 等到sum的值大于等于s时,就要开始移动左指针left,移动的同时还要将sum减去左边指针的值
- 移动左指针主要是为了求子数组最小的长度,将其与之前的的结果进行对比,取最小值
- 按照上面的步骤遍历数组,直至右指针指向数组的最后一个值,就结束遍历。
3. 代码实现
/**
* @param {number} s
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function(s, nums) {
let left = 0, right = 0, res = Infinity, sum = 0
while(right < nums.length){
sum += nums[right]
while(sum >= s){
res = Math.min(res, right - left + 1)
sum -= nums[left]
left ++
}
right ++
}
return res == Infinity ? 0 : res
};