问题描述

给定一个整数数组和一个整数 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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

性质：

1. 设子数组 nums[0 ... i] 中所有元素之和为 sum_i，子数组 nums[0 ... j] 中所有元素之和为 sum_j，且 i < j，那么子数组 nums[i + 1 ... j] 中所有元素之和为 sum_j - sum_i

2. 创建哈希表 d，若以 0 为起始索引的、所有元素之和为 sum 的子数组的数量为 n，则令 d[sum] = n。比如当 nums = [-1, 0, 1, 0] 时，d[-1] = 2、d[0] = 2

从前向后遍历 nums，设遍历到索引为 i 的分量时，nums[0 ... i] 中所有元素之和为 sum，执行：

• d[sum] = d.get(sum, 0) + 1

• 如果 sum - k（k 为目标值） 在 d 中，那么说明以 i 为终止索引的、和为 k 的连续子数组的数量为 d[sum - k]

Python 实现

class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        ret = 0
        d = {0: 1}
        sum = 0

        for number in nums:
            sum = sum + number
            if sum - k in d:
                ret = ret + d[sum - k]
            d[sum] = d.get(sum, 0) + 1

        return ret