Leetcode 209. Minimum Size Subarray Sum

@(Algo Probs)[LeetCode, Algorithm, Two Pointers]

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.

For 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.

---

Solution

In this approach, every subarray whose cummulative sum is greater than or equals to s will be checked. Although there are nested loop, the whole algorithm is in O(n) time.

该方法在O(n)时间内对所有和大于s的子串进行了遍历。注：尽管有嵌套的循环，但是任然是O(n)时间复杂度，因为内层的循环while(sum >= s)执行的总次数不会超过size次。

class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int size = nums.size(); int head = 0, sum = 0, ret = size + 1; for(int i = 0; i < size; i++) { sum += nums[i]; while(sum >= s) { ret = min(ret, i - head + 1); sum -= nums[head++]; } } return (ret == size + 1 ? 0 : ret); } };