[algorithm] sword finger offer2 golang interview question 10: subarray with sum K

[ Algorithm ] The finger of the sword offer2 golang Interview questions 10： And for k Subarray

subject 1:

Ideas 1: violence

Time complexity O(n2)

Code

func subarraySum(nums []int, k int) int {
    
    //start: 13:51, 13:57 
    // Ideas 1:  violence , Because there may be negative numbers in elements 
    // Fix a number i, Record the possibility behind 
    
    // Parameter checking 
    if len(nums) == 0 {
    
        return 0
    }

    // violence 
    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 
}

test 1

Ideas 2: The prefix and + hashmap

Because there are negative numbers , Therefore, sliding windows cannot be used

Code

func subarraySum(nums []int, k int) int {
    
    //start: 13:51, 13:57 
    // Ideas 2:  The prefix and  + hashmap
    //

    // Parameter checking 
    if len(nums) == 0 {
    
        return 0
    }

    // Prefix and + hashmap
    sumToCount := make(map[int]int)
    sum,resCount := 0,0
    sumToCount[0] = 1
    for i := 0; i < len(nums); i ++{
    
        sum += nums[i]
        // There is  sum - sumOld = k, Add to result 
        resCount += sumToCount[sum - k]
        sumToCount[sum] += 1
    }
    return resCount 
}

test