leetcode523-- Continuous Subarray Sum

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.

这个题目和第560题不太一样,这里也是连续的子数组的和,但是不再是等于一个具体的数了,而是只要是它的倍数,即能够整除它的时候就可以了,之前那个题用的思路是

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,

所以现在只需要每次循环建立字典的时候是以sumb%k建立字典(k!=0) ,sumb(k==0),建立字典,那么在建立字典先查一下之前有没有出现suma%ksuma (k==0)的时候,就可以了,

但是要注意特殊情况,这里要求必须至少是2个,所以两个字典的值的差要大于1才可以,

特殊情况是前两个数就直接满足了,但是这时候1-0=1, 所以初始化字典为dic[0]=-1, 这样1-(-1)>1就会满足了

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

注意 上面有很多数学道理在里面.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦