前缀和、哈希用法总结

思路：遇到这种连续子数组的问题，通常有的方法：

• 滑动窗口法（先通过移动right到达包涵要求的解，然后left再优化，而这个题目不符合这种要求）
• 动态规划（最长连续上升子序列）
• 前缀和

1.【leetcode560】和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

思路：前缀和根本思路在于推导presum[j] - presum[i - 1] = sum(i, j)，如果presum[j] - presum[i - 1]=k,那么presum在生成的过程中，利用哈希表查找是否存在presum-k的元素存在，记录presum-k存在的次数即为和presum组合的子数组的个数；还要注意边界即一个元素也需要记录个数。

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        hashmap = {0:1}
        presum = 0
        res = 0
        for i in range(len(nums)):
            presum += nums[i]
            if presum - k in hashmap:
                res += hashmap[presum - k]
            hashmap[presum] = hashmap.get(presum, 0) + 1
        return res

2.【leetcode974】 和可被 K 整除的子数组

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

示例：

输入：A = [4,5,0,-2,-3,1], K = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

思路：推导过程presum[j] - presum[i - 1] = sum(i, j),若数字a和b分别除以数字c，若得到的余数相同，那么(a-b)必定能够整除c，这里哈希表存储的是余数。

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        presum = 0
        res = 0
        a = 0
        hashmap = {0:1}
        for i in range(len(A)):
            a += A[i]
            presum = a % K
            if presum in hashmap:
                res += hashmap[presum]
            hashmap[presum] = hashmap.get(presum, 0) + 1
        return res

3.【leetcode523】

思路：这个哈希的键值是余数和索引值，注意初始情况，k==0的情况

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        #注意：1.k == 0;2.至少包括两个数i - hashmap[presum] > 1;3.使用if presum in hashmap:而不是hashmap.get(presum)
        res = False
        if len(nums) == 0:
            return res
        hashmap = {0:-1}
        presum = 0
        a = 0
        for i in range(len(nums)):
            a += nums[i]
            presum = a % k if k != 0 else a
            # print(hashmap.get(presum))存索引时不要这样，因为可能下标为0这样就跑到else那里去了
            if presum in hashmap:
                # print(i, hashmap[presum])
                if i - hashmap[presum] > 1:
                    res = True
            else:
                hashmap[presum] = i
            # print(hashmap)
        return res