523. Continuous Subarray Sum
https://leetcode.com/problems/continuous-subarray-sum/
solution
根据mode的数学特点, 前缀+贪心
prefix的精华在于两个不同位置的prefix相减, 据此怎么玩就需要随机应变(多练习)
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
if len(nums) < 2:
return False
prefix_sum = 0
mydict = {0: -1} # 注意包含第一个元素的序列, 如果第一个元素到中间元素可以被整除, [13, 2], 3
# 同时题目要求至少2个元素, 如果是前两个的和,也就是需要一个-1
for i, num in enumerate(nums):
prefix_sum += num
# 如果两个数除k都余同一个a,那么二者之差可以整除k
remainder = prefix_sum % k
if remainder not in mydict: # 先判断不在, 记录每个元素记录最早的index
mydict[remainder] = i
if i - mydict[remainder] >= 2: # 题目要求至少2个元素和
return True
return False
时间复杂度:O(n) 空间复杂度:O(n)
follow up
tricky的地方也在于,类似mode,通过hash记录了状态(而且是记录最早状态),然后当前状态与hash中状态可以组成目标
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
prefix_sum = 0
prefix_hash = {0: -1} # 初始化解决了 f([0, 1]) = 2
res = 0
for i, num in enumerate(nums):
if num == 1:
prefix_sum += 1
else:
prefix_sum -= 1
if prefix_sum in prefix_hash:
res = max(res, i - prefix_hash[prefix_sum])
else:
prefix_hash[prefix_sum] = i
return res
Last updated