209. Minimum Size Subarray Sum

[tech-cow]

209. Minimum Size Subarray Sum

公瑾回来刷题咯

"""
[start] 12:34

Problem Solving Thought Process:

1. Brute Force
Using 2 for loops to find out 2 element that sums up to the target
Constantly update the minimum length in a globalMin

globalMin = infi
for i -> n
    for j -> n
        cur_sum += nums[j]
        if cur_sum > target:
            globalMin = min(globalMin, cur_sum)
            break
return globalMin

Time: O(N^2)
Space: O(1)


2. Two Pointer 
We can potentially only iterate "j" from beginning to end once by moving "i" along the way

Time: O(N)
Space: O(1)
"""

#[Coding Start] 12:39
#[Coding Finish] 12:43
#[Eyeballing code] 12:43 - 12:46
# Bug
"""
globalMin = float('inf')
curSum = 0
j = 0

for i in range(len(nums)):
    while j < len(nums) and curSum < target:
        curSum += nums[j]
        j += 1

    if curSum >= target:
        globalMin = min(globalMin, j - i)

    curSum -= nums[i]

return globalMin   ->  bug1. 如果没有找到合适的结果，应该返回0而不是初始值的infinite

fail testcases:

3
[1,1]
"""
        
class Solution(object):
    def minSubArrayLen(self, target, nums):      
        globalMin = float('inf')
        curSum = 0
        j = 0
        
        for i in range(len(nums)):
            while j < len(nums) and curSum < target:
                curSum += nums[j]
                j += 1
            
            if curSum >= target:
                globalMin = min(globalMin, j - i)
            
            curSum -= nums[i]
        
        return globalMin if globalMin != float('inf') else 0