560 和为K的子数组（枚举、前缀和、哈希表）

╰半橙微兮° 2022-08-31 07:16 179阅读 0赞

**1. 问题描述：**

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

**示例 1 :**

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

**说明 :**

数组的长度为 \[1, 20,000\]。  
数组中元素的范围是 \[-1000, 1000\] ，且整数 k 的范围是 \[-1e7, 1e7\]。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/subarray-sum-equals-k

**2. 思路分析：**

对于这种题目我们首先需要考虑怎么样枚举才可以将所有答案枚举出来，一般枚举的是以当前位置i为终点的...对于这道题目来说可以枚举以当前位置i为终点的所有区间，使得s\[i\] - s\[j\] = k，其中s\[i\]，s\[j\]为\[1，i\]和\[1，j\]位置的前缀和，这样枚举肯定是可以将所有答案枚举出来。当区间终点i固定之后那么我们希望是找到区间起点j，使得s\[j\] = s\[i\] - k，j = 1，2，... i - 1，怎么样找到这个位置j呢？我们可以在遍历的时候使用**哈希表**来维护到当前位置的前缀和这样对于当前的位置i，检查s\[i\] - k是否存在即可，如果存在说明存在区间\[i + 1，j\]使得区间和为k，因为求解的是总的区间个数所以我们需要维护在哈希表中维护前缀和出现的次数，这样就可以求解出以当前位置i为区间终点的满足s\[i\] - s\[j\] = k的区间个数。这是一道非常经典的**前缀和 + 哈希表**优化的题目，我们可以记住其中的思路，特别是题目中蕴含的枚举，前缀和 + 哈希表优化的思想。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**3. 代码如下：**

from typing import List
    import collections
    
    
    class Solution:
        # 前缀和 + 哈希表
        def subarraySum(self, nums: List[int], k: int) -> int:
            dic = collections.defaultdict(int)
            # 边界
            dic[0] = 1
            # s表示前缀和
            s = 0
            res = 0
            for x in nums:
                s += x
                # 判断是否存在区间起点j使得si - sj == k,也即判断哈希表中是否存在s[i] - k 
                if dic[s - k] > 0:
                    res += dic[s - k]
                # 维护当前前缀和的出现次数
                dic[s] += 1
            return res

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/5b49e3f91054448f9973f6ba2ec78da2.png