Description
Notes
Testcase
Judge
Given an array of 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.
Have you met this question in a real interview? Yes
Example
Given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.
Challenge
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
Tags
Array Two Pointers Facebook
Related Problems
Medium Subarray Sum Closest 20 %
Easy Subarray Sum 30 %
class Solution {
public:
/\*\*
\* @param nums: a vector of integers
\* @param s: an integer
\* @return: an integer representing the minimum size of subarray
\*/
int minimumSize\(vector<int> &nums, int s\) {
// write your code here
if \(nums.empty\(\)\) {
return -1;
}
int len = INT\_MAX;
int j = 0, sum = 0;
for \(int i = 0; i < nums.size\(\); ++i\) {
while \(sum < s && j < nums.size\(\)\) {
sum += nums\[j\];
++j;
}
if \(sum >= s\) {
if \(j - i < len\) {
len = j - i;
}
sum -= nums\[i\];
}
}
if \(len == INT\_MAX\) {
return -1;
}
return len;
}
};