560. 和为 K 的子数组 - 力扣（Leetcode）

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

枚举

我们可以用i作为索引，从i开始遍历后面的数的和，出现和为k的时候结果增加。

func subarraySum(nums []int, k int) int {
    var sum int
    var ans int
    for i:=range nums {
        sum=0
        for j:=i;j<len(nums);j++{
            sum+=nums[j]
            if sum==k {
                ans++
            }
        }
    }
    return ans
}

时间复杂度为O(n^2),空间复杂度为O(1)
很显然，这个方法很拙劣

前缀和+哈希表优化

这个方法看起来很高端，但其实也还好
前缀和就不必多说了吧，[0,sum[1],....sum[n]],sum[n]为前n项数的和。
那么区间和，就可以理解为
sum[i]−sum[j−1]==k (i<=j)
移项可知
sum[j−1]==sum[i]−k (i>=j)
所以说，我们可以将前n项前缀和用map记录起来，以i为元素遍历sum，若map存在sum[i]-k,则增加相应个数。

func subarraySum(nums []int, k int) int {
    maps:=make(map[int]int,len(nums))
    count:=0
    maps[0]=1
    ans:=0
    for _,o:=range nums {
        count+=o
        if val,ok:=maps[count-k];ok{
            ans+=val
        }
        maps[count]++
    }
    return ans
}

时间复杂度O(n)，空间复杂度O(n)

Q.E.D.