Python 52 ms-using cum sum mode k.


  • 0
    W

    Python 52ms, 67%. The problem can be transformed to a problem about same remainder mode k for cum sum of original list. So dictionary should be used to remember remainder. However, based on pigeonhole principle, when length of list larger than k, it should have true.
    '''
    class Solution(object):
    def checkSubarraySum(self, nums, k):
    if k==0:
    for i in range(len(nums)-1):
    if nums[i]==0 and nums[i+1]==0:
    return True
    return False
    if k<0: k=-k
    dic={}
    s=0
    dic[0]=-1
    for i in range(len(nums)):
    s=(s+nums[i])%k
    if s not in dic: dic[s]=i
    elif i-dic[s]>=2: return True
    return False
    '''


Log in to reply
 

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