Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

862. Shortest Subarray with Sum at Least K #74

Open
tech-cow opened this issue Jan 14, 2020 · 0 comments
Open

862. Shortest Subarray with Sum at Least K #74

tech-cow opened this issue Jan 14, 2020 · 0 comments

Comments

@tech-cow
Copy link
Owner

862. Shortest Subarray with Sum at Least K

'''

思路参考:https://github.com/Shellbye/Shellbye.github.io/issues/41
Time: O(N^2) TLE 

Brute Force + preSum 思路:
在Brute Force的基础上,加入一个PreSum来记忆化记忆一下到i为止的和,方便与之后直接调用

注意的事项就是要给preSum多预留一个位置,和DP类似,用来处理一些edge case,比如array总长就一个

Input: A = [1], K = 1
Output: 1
    
这个例子如果用 preSum[j] - preSum[i] 而不预留位置, preSum则为[1] ,由于两个位置重叠,减后的0
应该是给与额外的preSum位置,preSum则为[0, 1] 这样及时相减也能够得到1。 (1 - 0)
另外就是i和j的for循环分别多走一位,为了匹配多出来的一位preSum

'''

class Solution(object):
    def shortestSubarray(self, nums, target):
        preSum = [0]
        globalMin = float('inf')
        
        for num in nums:
            preSum.append(preSum[-1] + num)
        
        for i in range(len(nums) + 1):
            for j in range(i, len(nums) + 1):
                if preSum[j] - preSum[i] >= target:
                    globalMin = min(globalMin, j - i)    
        
        return globalMin if globalMin != float('inf') else -1
'''
Time: O(N)
Space: O(N)


两个While Loop

第一个While Loop用于滑动窗口的中的,移动左边指针的操作
当preSum[i]减去queue里面最左边,也就是queue里面最小的index的时候(因为queue里存的是index,所以是升序排序的,queue[0]就可以理解为最小的数)
    如果满足超过target大小,我们保存在globalMin并且可以开始移动左边的指针了,所以这里queue.popleft掉了最左边的指针。

    
第二个While Loop用来删掉负数
    如果在preSum的数组里面,当前的preSum[i]要大于之前加进去的数的话,比如preSum[2] = 100, preSum[3] = 50, 说明从2-3的过程中,sum小了50,所以是加到了-50,加了一个负数。
    我们为了求取最小的subarray,负数的就要果断移除
'''


from collections import deque
class Solution(object):
    def shortestSubarray(self, nums, target):
        globalMin = float('inf')
        preSum = [0]
        for num in nums:
            preSum.append(preSum[-1] + num)
        
        queue = deque()
        for i in range(len(nums) + 1):
            while queue and preSum[i] - preSum[queue[0]] >= target:  
                globalMin = min(globalMin, i - queue.popleft())  
                
            while queue and preSum[queue[-1]] >= preSum[i]:
                queue.pop()
            queue.append(i)
        return globalMin if globalMin != float('inf') else -1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant