209. Minimum Size Subarray Sum
难度: Medium
刷题内容
原题连接
- https://leetcode.com/problems/minimum-size-subarray-sum
内容描述
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
Example:
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.
解题方案
思路 1 **- 时间复杂度: O(N)*- 空间复杂度: O(N)***
算法来源于知乎文章——趣味算法思想 * 这里可以看到由于需要找连续的子数组，所以依旧可以设置两个指针，往同一方向移动。 * 如果两个指针中间的值加起来>sum的时候，记录此时数组的长度，接着左指针移动，减小sum的值 ； * 如果< sum的话，右指针移动扩大范围。 * 最后返回最短的长度值。
代码：
/**
* @param {number} s
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function(s, nums) {
var left = 0;
var right = -1; // right 的起始位置很重要，这里选择-1 [left, right]这个区间刚开始是没有值的
var tmpSum = 0;
var minLength;
// 循环停止的条件是左指针小于长度
while (left < nums.length - 1) {
if(tmpSum < s) {
// 这里要注意边界的处理，当右指针移动到最后一个元素的时候结束
if(right >= nums.length -1) {
return minLength || 0;
}
right ++;
// 这里tmpSum的计算也很巧妙，直接用累加的方式，节省计算量
tmpSum = tmpSum + nums[right]
} else {
var tmp = right - left + 1;
if(minLength) {
if(tmp < minLength) {
minLength = tmp;
}
} else {
minLength = tmp;
}
// 左边指针移动减少sum的值
tmpSum = tmpSum - nums[left];
left ++;
}
}
if(!minLength) {
return 0;
}
return minLength;
};
