Simple hashing Python O(n)


  • 0
    E

    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.