Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.



Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.




Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.



Note:

The length of the array won't exceed 10,000.
You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

Difficulty: interview

Starter code:

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        

Solutions:
class Solution:
     def checkSubarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         if k==0:
             j=0
             for i in range(0,len(nums)):
                 if nums[i]==0:
                     if j<i:
                         return True
                 else:
                     j=i+1
             return False
         dic={0:-1}
         c=0
         for i in range(0,len(nums)):
             c=(c+nums[i])%k
             if c in dic:
                 if i-dic[c]>1:
                     return True
             else:
                 dic[c]=i
         return False

class Solution:
     def checkSubarraySum(self, nums, k):
         dict,cur = {},0
         if k == 0:
             zero = 0
             for i in nums:
                 if i == 0 and zero == 1:
                     return True
                 elif i == 0 and zero != 1:
                     zero = 1
                 else:
                     zero = 0
             return False
         for i in range(len(nums)):
             cur += nums[i]
             if i!= 0 and cur % k == 0:
                 print('1')
                 return True
             elif cur % k in dict and cur >= k:
                 print('2')
                 return True
             elif i!= 0 and nums[i] == 0 and nums[i-1] == 0:
                 print('3')
                 return True
             else:
                 dict[cur % k] = True
         return False
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """


class Solution:
     def checkSubarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
 
         if not nums or len(nums) < 2:
             return False
 
         k = abs(k)
         n = len(nums)
         d = {0:-1}
         sum = 0
         for i in range(n):
             sum += nums[i]
             key = sum % k if k > 0 else sum
             
             if key not in d:
                 d[key] = i
             elif i >= d[key] + 2:
                 print(d[key] + 1, i)
                 return True
 
         return False

class Solution:
     def checkSubarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         if not nums or len(nums) < 2:
             return False
 
         if k == 1:
             return True
 
         cur_sum, sums = 0, {0: -1}
         for i, x in enumerate(nums):
             cur_sum += x
             mod = (cur_sum % k) if k != 0 else cur_sum
             if mod in sums:
                 if i - sums[mod] >= 2:
                     return True
             else:
                 sums[mod] = i
         return False

class Solution:
     def checkSubarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         if k==0:
             i=1
             while i<len(nums):
                 if nums[i-1]==0 and nums[i]==0:
                     return True
                 i+=1
             return False    
         d=dict()
         d[0]=-1
         s=0
         for i,x in enumerate(nums):
             s+=x
             s=s%k
             if s in d :
                 if i-d[s]>1:
                     return True
             else:    
                 d[s]=i
         return False    


class Solution(object):
     def checkSubarraySum(self, nums, k):
 
         
         if k == 0:
             # if two continuous zeros in nums, return True
             # time O(n)
             for i in range(0, len(nums) - 1):
                 if nums[i] == 0 and nums[i+1] == 0:
                     return True
             return False
         
         k = abs(k)
         if len(nums) >= k * 2:
             return True
         
         #if n >= 2k: return True
         #if n < 2k:  time O(n) is O(k)  
 
         sum = [0]
         for x in nums:
             sum.append((sum[-1] + x) % k)
         
         Dict = {}
         for i in range(0, len(sum)):
             if sum[i] in Dict:
                 if i - Dict[sum[i]] > 1:
                     return True
             else:
                 Dict[sum[i]] = i
         
         return False

class Solution:
     def checkSubarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         sum = 0
         indices = {0: -1}
         for i in range(len(nums)):
             sum += nums[i]
             if k == 0:
                 l = indices.get(sum)
                 if l is not None and i - l >= 2:
                     return True
                 elif l is None:
                     indices[sum] = i
             else:
                 l = indices.get(sum % k)
                 if l is not None and i - l >= 2:
                     return True
                 elif l is None:
                     indices[sum % k] = i
         return False


class Solution:
     def checkSubarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         if not nums or len(nums) <= 1:
             return False
         if k == 0:
             for i in range(1, len(nums)):
                 if nums[i] == 0 and nums[i-1] == 0:
                     return True
         else:
             nums[0] = nums[0] % k
             for i in range(1, len(nums)):
                 nums[i] = (nums[i-1] + nums[i]) % k
                 if nums[i] == 0:
                     return True
             numdict = {}
             for i in range(len(nums)):
                 if nums[i] not in numdict:
                     numdict[nums[i]] = i
                 elif i > numdict[nums[i]] + 1:
                     return True
         # for i in range(len(nums)):
         #     for j in range(i+1, len(nums)):
         #         if sum(nums[i:j+1]) % k == 0:
         #             return True
         return False


class Solution:
     def checkSubarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         indexs = {}
         indexs[0] = -1
         curr_sum = 0
         for i in range(len(nums)):
             if k != 0:
                 curr_sum += nums[i]
                 modv = curr_sum % k
                 if modv in indexs and i - indexs[modv] > 1:
                     return True
                 if not modv in indexs:
                     indexs[modv] = i
             else:
                 if nums[i] == 0 and i < len(nums) - 1 and nums[i+1] == 0:
                     return True
         return False

class Solution:
     def checkSubarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         if not k:
             i=0
             while i<len(nums)-1:
                 if not nums[i] and not nums[i+1]:
                     return True
                 i+=1
             return False
         k=abs(k)
 
         dic={0:-1}
         rem=0   # remainder
         i=0
         while i< len(nums):
             rem=(rem+nums[i])%k
             if rem not in dic: dic[rem]=i
             elif dic[rem]<i-1: return True
             i+=1
         return False
 


class Solution:
     def checkSubarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         s = 0
         dic = collections.defaultdict(list)
         dic[0].append(-1)
         
         for i in range(0, len(nums)):
             s +=nums[i] 
             if k==0:
                 dic[s].append(i)
                 if i-dic[s][0]>1:
                     return True
             else:
                 dic[s%k].append(i)
                 if i-dic[s%k][0]>1:
                     return True
         
         return False


class Solution:
     def checkSubarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         if k == 0:
             for i in range(len(nums) - 1):
                 if nums[i] == nums[i + 1] == 0:
                     return True
             return False
         if len(nums) <= 1:
             return False
         s = 0
         acc = []
         for n in nums:
             s += n
             s %= k    
             acc.append(s)
         for i in range(1, len(nums)):
             if acc[i] == 0:
                 return True
         return len(set(acc)) != len(acc)


class Solution:
     def checkSubarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: bool
         """
         P = [0]
         for x in nums:
             v = P[-1] + x
             if k: v %= abs(k)
             P.append(v)
 
         seen = set()
         for i in range(len(P) - 3, -1, -1):
             seen.add(P[i+2])
             if P[i] in seen:
                 return True
         return False