前缀和

暴力

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

前缀和

个人对前缀和的理解，欢迎交流
s0 = 0
s1 = x1
s2 = x1+x2 =s1+x2
s3 = x1+x2+x3 = s2+x3 = s1+x2+x3
s4 = x1+x2+x3+x4 = s1+x2+x3+x4 = s2+x2+x3+x4 =s3 +x4
sum[i:j] 表示i到j的和 区间是各种语言通用的左闭右开，如下s4的和可表示成如下形式
sum[:5]-sum[:2] = sum[2:5]，
sum[:5]-sum[:3] = sum[3:5]，
sum[:5]-sum[:4] = sum[4:5]，
也就意味着 sum[:i]-s[:j]= sum[j:i]。
因此 已知当前项的sum 和需要查找的k，k表示的是sum[j:i]，j到i的连续和， sum[:i]-sum[j:i]=sum[:j] 也就要查找sum[:j]的和，也就是0到j的和 也就大家的所说的前缀和
为了避免重复计算 我们可以把当前sum[:j] 存储到hash中，因为存在正负数，也就意味着可能存在多个这样的sum[:j]

func subarraySum(nums []int, k int) int {
    m := map[int]int{0:1}
    var sum int
    var count int
    for i :=0;i<len(nums);i++{
        sum +=nums[i]
        if v,ok:=m[sum-k];ok{
            count+=v
        }
        m[sum]++
    }
    return count
}