首页 > 技术文章 > Leetcode 523. Continuous Subarray Sum

zywscq 2019-03-18 01:49 原文

prefix sum

class Solution(object):
    def checkSubarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        if k == 0:
            return any(nums[i - 1] == 0 and nums[i] == 0 for i in range(1, len(nums)))
        book, s = {0: 0}, 0
        for i, v in enumerate(nums):
            s = (s + v) % k
            j = book.get(s, -1)
            if (j != -1) and i+1 - j > 1:
                return True
            if s not in book:
                book[s] = i+1
        return False

 

推荐阅读