一天一大 leet(长度最小的子数组)难度:中等 DAY-28
题目(难度:中等):
给定一个含有 n 个正整数的数组和一个正整数 s，找出该数组中满足其和 ≥s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
示例
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。抛砖引玉
特殊情况
- nums 为空返回 0
逻辑
- 循环数组，分别以每个元素当做开始找到其一直连续的数组，开始的索引 start，结束的索引 end
- 记录每个 start 和 end 对应的和
- 判断其和是否大于等于 s
- 如果等于在本次 start 和 end 的距离与之前记录的距离中取最小值
/**
* @param {number} s
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function (s, nums) {
let len = nums.length
if (len == 0) {
return 0
}
let _result = Number.MAX_VALUE
for (let start = 0; start < len; start++) {
let sum = 0
for (let end = start; end < len; end++) {
sum += nums[end]
if (sum >= s) {
_result = Math.min(_result, end - start + 1)
break
}
}
}
return _result == Number.MAX_VALUE ? 0 : _result
}官方答案
- 双指针
- 利用 start 和 end 双指针计算满足条件的子数组之和；
- 计算完一组满足条件数组之后后，减掉开始位置数据，指针向后移动一位
/**
* @param {number} s
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function (s, nums) {
let n = nums.length
if (n == 0) {
return 0
}
let ans = Number.MAX_VALUE
let start = 0,
end = 0
let sum = 0
while (end < n) {
sum += nums[end]
while (sum >= s) {
ans = Math.min(ans, end - start + 1)
// 本轮满足条件的连续子集已得到，减start位置的子集
sum -= nums[start]
// start指针向后移动一位
start++
}
end++
}
return ans == Number.MAX_VALUE ? 0 : ans
}举报
腾讯云开发者
