Simple hashing Python O(n)

  • 0

    Use the fact that (x-y)%z = (x%z) - (y%z). We can store the mod values of each sum instead. For duplicates, just store the earliest occurrence as doing so will maximize the length to get by the requirement of at least size 2.

        def checkSubarraySum(self, nums, k):
            :type nums: List[int]
            :type k: int
            :rtype: bool
            if not nums: return False
            cache, _sum = {}, 0
            for i,v in enumerate(nums):
                _sum += v
                m = _sum % k if k != 0 else _sum
                if (m == 0 and i > 0) or i-cache.get(m,i) > 1: return True
                if m not in cache: cache[m] = i
            return False

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.