第一周: Two Pointer

[tech-cow]

No description provided.

[tech-cow]

Day 1

Medium

• 209. Minimum Size Subarray Sum
• 3. Longest Substring Without Repeating Characters

Hard

• 862. Shortest Subarray with Sum at Least K

Day 2

Count Number of Nice Subarrays
Replace the Substring for Balanced String
Max Consecutive Ones III
Binary Subarrays With Sum
Subarrays with K Different Integers
Fruit Into Baskets
Shortest Subarray with Sum at Least K

Hard

• 76. Minimum Window Substring
• 340. Longest Substring with At Most K Distinct Characters

More Sliding Window:

[tech-cow]

Day 1

Medium

• 209. Minimum Size Subarray Sum
• 3. Longest Substring Without Repeating Characters

Hard

• 862. Shortest Subarray with Sum at Least K

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

3. Longest Substring Without Repeating Characters

globalSet这块看了下答案，没完全写对，再刷一次

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        globalMax = -float('inf')
        globalSet = set()
        j = 0
        
        for i in range(len(s)):
            while j < len(s) and s[j] not in globalSet:
                globalSet.add(s[j])
                globalMax = max(globalMax, len(globalSet))
                j += 1
            globalSet.remove(s[i])
        
        return globalMax if globalMax != -float('inf') else 0

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

[tech-cow]

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