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

题目1:

思路1: 暴力

时间复杂度 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 
}

测试1

思路2: 前缀和 + hashmap

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

代码

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 
}

测试