Description:
https://leetcode.com/problems/minimum-size-subarray-sum/#/description
Boundary:
- if sum of nums() < s, there is no proper subarray.
Algorithm:
My first solution:
Just gets sum of the 0-th element to the k-th element: sum[k+1]. Then the sum of the i-th element to the j-th element will be sum[j] – sum[i].
Then traverse i from 0 to nums.size() to find the start of the subarray.
Then traverse j from i+1 to nums.size() + 1 to find the end of the subarray.
Find the min length, and replace the older one if shorter.
However, the timing is not good.
Whether to get sum initially? I remember some problems about subarray which got sum initially. However, we don’t need it in this problem.
Second solution ( O(n) ):
Count from the 0-th element and find sum[j] > s with min j.
Gradually shorten the subarray by subtracting the element at the beginning of the subarray until sum[j] < s.
Extend at the tail and shorten at the beginning.
Code:
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int begin = 0;
int end = 0;
int n = nums.size();
int sum = 0;
int length = INT_MAX;
while (end < n)
{
sum += nums[end++];
while (sum >= s)
{
length = min(end – begin,length);
sum -= nums[begin++];
}
}
return length == INT_MAX ? 0: length;
}
};
Explanation:
Well, you may wonder how can it be O(n) since it contains an inner while loop. Well, the key is that the while loop executes at most once for each starting position start. Then start is increased by 1 and the while loop moves to the next element. Thus the inner while loop runs at most O(n) times during the whole for loop from 0 to n - 1. Thus both the for loop and while loop has O(n) time complexity in total and the overall running time is O(n). (Cited from: https://discuss.leetcode.com/topic/17063/4ms-o-n-8ms-o-nlogn-c)