n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn‘t one, return -1 instead.Example 1:
Input: [2,3,1,2,4,3], s = 7
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:
Input: [1, 2, 3, 4, 5], s = 100
Output: -1
If you have figured out the O(nlog n) solution, try coding another solution of which the time complexity is O(n).
思路：
用两根指针对数组进行一次遍历即可.
如果当前和小于s, 右指针右移, 扩大区间, 反之左指针右移, 缩小区间.
在这个过程中维持区间的和不小于s, 然后更新答案即可.
public class Solution {
/**
* @param nums: an array of integers
* @param s: An integer
* @return: an integer representing the minimum size of subarray
*/
public int minimumSize(int[] nums, int s) {
int ans = Integer.MAX_VALUE;
int i, j = 0;
int sum = 0;
//for 循环主指针
for (i = 0; i < nums.length; i++) {
sum += nums[i];
// while 循环辅指针
while(j < nums.length && sum >= s) {
ans = Math.min(ans, i - j + 1);
sum -= nums[j];
j++;
}
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
}
原文：https://www.cnblogs.com/FLAGyuri/p/12078519.html