https://leetcode.com/problems/minimum-size-subarray-sum/
Minimum Size Subarray Sum
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 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.
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.
Code
import sys
class Solution(object):
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
p1 = p2 = 0
cum = 0
min_len = sys.maxint
for num in nums:
cum += num
if cum >=s:
min_len = min(min_len, p1-p2+1)
while p2 < p1:
if cum-nums[p2] >=s:
cum = cum-nums[p2]
p2 += 1
min_len = min(min_len, p1-p2+1)
else:
break
p1 += 1
return 0 if min_len == sys.maxint else min_len
Idea
Remember that all numbers are positive. You can have a fast pointer `p1` and a slow pointer `p2`. You first make the fast pointer to traverse the numbers until sum from nums[p2] to nums[p1] is more than s. Then, you start to move `p2` forward until the sum from nums[p2] to nums[p1] is no more than s anymore. In total, `p1` and `p2` both traverse at most O(N) distance. So the time complexity of the algorithm is O(N). Since we don’t require additional space, the space complexity of the alogrithm is O(1).