leetcode
leetcode copied to clipboard
Published
20 hours ago •
tech-cow
tech-cow
第一周: Two Pointer
Day 1
Medium
Hard
- [x] 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
More Sliding Window:
Day 1
Medium
Hard
- [x] 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
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