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: 2Explanation: the subarray [4,3] has the minimal length under the problem constraint.Follow up:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
难度：medium
题目：给定一个包含正整数的数组和一个正整数 s，找出最小长度且元素相连的子数组使得其和大于 s. 如果不存在这样的子数组，则返回 0.
思路：滑动伸缩窗口。滑动窗口左边界为 start index, 右边界为 i, 窗口为 [start index, i].
Runtime: 2 ms, faster than 99.88% of Java online submissions for Minimum Size Subarray Sum.
class Solution {
// O(2n)
public int minSubArrayLen(int s, int[] nums) {
int sum = 0, startIdx = 0;
int minLen = nums.length + 1;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum >= s) {
// shrink window
while (startIdx <= i && sum >= s) {
minLen = Math.min(minLen, i – startIdx + 1);
sum -= nums[startIdx++];
}
}
}
return minLen > nums.length ? 0 : minLen;
}
}