Golang concise, commented, O(N)

  • 0
    func subarraySum(nums []int, k int) int {
        // Implicit subarray with sum 0 at the beginning of the array, accounts for sum(0...(n-1)) == 0, val(n)==k case
        m := map[int][]int{0:[]int{-1}}
        sum, count := 0, 0
        for i, v := range nums {
            sum += v
            if s, ok := m[sum-k]; ok { // Do we have one or more subarrays 0...i that sum to (sum - k)? If yes, means i+1...n sums to k
                count += len(s)        // We add each such subarray
            m[sum] = append(m[sum], i) // Do this step last, or we will allow zero-length arrays that throws the count off for k=0
        return count

Log in to reply

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