leetcode 523 523. 连续的子数组和

原题

1. 还是需要再看看。
2. 见注释。

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        """
        # 一下这种写法本来就是最暴力的，现在又跟除以0干上了
        # 看了官方题解，这道题跟数学有关。
        对于这个例子： [23,2,4,6,7], k = 6
            由于 sum([23, 2, 4]) == 29  and 29 % 6 = 5
                 sum([23, 2, 4, 6]) = 35 and 35 % 6 = 5 
           那么 下标 [2， 3] 闭区间 就算结果。 

           真是没意思。
           如果真是说与动态规划有关的话，这道题用的是hashmap 来保存计算的结果，避免重复计算。
        """
        n = len(nums)
        if n < 2:
            return False 

        dic = {0:-1}        # d = {remainder : index } 遇到2个相等的余数，那么他们之间的index就是结果。
        _sm = 0
        for i in range(n):
            # 这里处理 除以0的问题也是很巧妙的。 

            # 下面的这3行。仔细理解一下，就是让上 一个子数组和的余数 来累加 原数组的下一个数，
            # 就等价于是在不停地消除 k的倍数。如果是真的与动态规划有关的话，那么就体现在这里了。
            _sm += nums[i]
            if k != 0:
                _sm = _sm % k
            if _sm in dic:

                if (i - dic[_sm]) > 1:
                    return True 
            else:
                dic[_sm] = i
        return False