Golang simple O(n) solution


  • 0

    The important facts are

    1. we just need to return a number of subarray
    2. If you have a sum from 0 to N and 0 to M, then you can calc the sum of N to M by sum[0:N] - sum[0:M]

    So, while iterating an element one by one, we calculate a sum of 0 to n, and store info to a hashmap which has sum value as key, a count how many that sum value appears so far as value.

    Then, when you have a sum of 0 to N, even the sum doesn't equal to k, if you know how many the sum N- k appears so far, the number can be added as an answer.

    func subarraySum(nums []int, k int) int {
    	cache := make(map[int]int)
    
    	res := 0
    	sum := 0
    	for i := 0; i < len(nums); i++ {
    		sum += nums[i]
    		if sum == k {
    			res += 1
    		}
    
    		if v, ok := cache[sum-k]; ok {
    			res += v
    		}
    
    		if v, ok := cache[sum]; !ok {
    			cache[sum] = 1
    		} else {
    			cache[sum] = v + 1
    		}
    	}
    	return res
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.