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

525. Contiguous Array

• 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