题目分析

连续子数组的和，一定会用得到前缀和概念，可以节省大量的计算。cursum数组表示前缀和，cursum[i]表示前i个元素的和。cursum[0] = 0，那么从第m个元素到第n个元素的连续子数组的和为cursum[n] - cursum[m - 1]。

哈希表

首先计算数组的前缀和，如果前缀和cursum[j] - cursum[i] = k，那么说明从第i + 1个元素到第j个元素组成的子序列之和为k。因此题目转换为遍历j，寻找满足cursum[i] = cursum[j] - k公式中i的个数。

将遍历过的数都加入哈希表，这样寻找满足公式中i的个数时直接取出即可。

注意此题是有顺序的，即i是小于j的，因此不能将所有cursum的值都存入哈希表，只能遍历过的点存入，这样才能保证取出的点都是小于j的。而有的题目是需要将cursum的值先全部存入哈希表，然后再进行遍历。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

from collections import defaultdict


class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        cursum, res, dic = 0, 0, defaultdict(int)
        dic[0] = 1
        for x in nums:
            cursum += x
            res += dic[cursum - k]
            dic[cursum] += 1
        return res

刷题总结

有趣的数组题，数组是笔试面试中的常考题型，表述简单，思路清晰，是小伙伴们需要加强的重点题型。