leetcode523-- Continuous Subarray Sum

# 小郑之家~

### 题目

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.



suma - sumb = k, 即suma-k=sumb， 所以每次就以sumbkey建立字典，并在每次建立字典之前先查找有没有suma-k这个key, 如果有的话，就返回结果了，即便是只有一个数，也要返回，

suma-sumb = nk,n为整数, 其实也还是用了上面的题的思想，对左边的这个式子同时关于k取模的话，可以得到

suma%k - sumb%k = 0, 前提是k != 0的时候才可以取模，如果k=0的话，就直接可以suma-sumb=0,

class Solution(object):
def checkSubarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""

# suma-sumb = n*k, suma-n*k = sumb

dic = {}
dic[0] = -1   # 防止出现[0,0] k=0.这种主要是防止前两个就满足条件的时候.

summ = 0
for i in range(len(nums)):
summ += nums[i]
if k==0:
t = summ
else:
t = summ%k

# 每次在建立字典之前都要先查找，这样永远都是suma-sumb.
if t in dic:
if (i-dic[t])>1:
return True
else:
dic[t] = i

return False