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.

Source: leetcode | Difficulty: MEDIUM
Tags: Mathematics

Data structures

Range queries

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

Solutions:
class Solution:

	def checkSubarraySum(self, nums, k):
		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


class Solution:

	def checkSubarraySum(self, nums, k):
		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):
		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):
		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:
			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
		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):
		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):
		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
		return False


class Solution:

	def checkSubarraySum(self, nums, k):
		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
			elif nums[i] == 0 and i < len(nums) - 1 and (nums[i + 1] == 0):
				return True
		return False


class Solution:

	def checkSubarraySum(self, nums, k):
		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
		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):
		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):
		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):
		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