LC-0523 Medium LeetCode

523. Continuous Subarray Sum

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 31% Topics: Array, Hash Table, Math, Prefix Sum

Reading material

Arrays & Hashing 12 min Math & Geometry 12 min Prefix Sums & Difference Arrays 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(k)

class Solution(object):
    def checkSubarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        count = 0
        lookup = {0: -1}
        for i, num in enumerate(nums):
            count += num
            if k:
                count %= k
            if count in lookup:
                if i - lookup[count] > 1:
                    return True
            else:
                lookup[count] = i

        return False

Solution from kamyu104/LeetCode-Solutions · MIT