[算法] 剑指offer2 golang 面试题10：和为k的子数组

时间复杂度 O(n2)

func subarraySum(nums []int, k int) int {
    //start: 13:51, 13:57 
    //思路1: 暴力,因为元素中有可能是负数
    //固定一个数字i,记录后面存在的可能性
    
    //参数校验
    if len(nums) == 0 {
        return 0
    }

    //暴力
    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 
}

因为有负数存在, 所以滑动窗口是不能用的

func subarraySum(nums []int, k int) int {
    //start: 13:51, 13:57 
    //思路2: 前缀和 + hashmap
    //

    //参数校验
    if len(nums) == 0 {
        return 0
    }

    //前缀和和+ hashmap
    sumToCount := make(map[int]int)
    sum,resCount := 0,0
    sumToCount[0] = 1
    for i := 0; i < len(nums); i ++{
        sum += nums[i]
        //存在 sum - sumOld = k,累加到结果中
        resCount += sumToCount[sum - k]
        sumToCount[sum] += 1
    }
    return resCount 
}