Intuition for storing the sum and frequency in a HashMap

Question

We are given an array of integers and another number k, and we need to find the total number of continuous subarrays, the sum of which is equal k. I found the following interesting snippet of LeetCode code:

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, sum = 0;
        HashMap < Integer, Integer > map = new HashMap < > ();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k))
                count += map.get(sum - k);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

I liked the efficient solution, and so I am trying to figure it out; however, I have two questions:

• What is the intuition for storing the current one sumand its frequencyin HashMap?
• What is the guarantee that the detected sub-barrier is continuous?

Input example: [1,1,1]and k = 2;
Output:2

Answer 1

Good algorithm.

: sum(1, i) = sum(1, j) + sum(j + 1, i) ( Java , ) i j.

sum(j+1, i) k.

, sum(1, i) = sum(1, j) + k sum(1, i) -k = sum(1, j)

sum(1, i) sum. , j, sum -k = sum(1, j) . , sum(1, j) map.

map.containsKey(sum - k), , j, .

.

PS: BTW, , . .

PPS: , Java 8

    for (int num : nums) {
        sum += num;
        count += map.getOrDefault(sum - k, 0);
        map.compute(sum, (key, value) -> (value == null) ? 1 : value + 1);
    }

Answer 2

nums[], map sum (sum ).

, , if, , map sum-k X , sum, , X k. , sum , map . map , , ( , num[] ). "" , .

Answer 3

3 :

• - 0
• count , sum - k

3 :

1st: .

1.
? , . - . , if (map.containsKey(sum - k)) sum - k. sum - k - , , (sum - k) , k ( k + (sum - k) = sum - ). , count - .

2nd: .
, . , , , count, 0 nums.
count.

. : subarraySum({0, 0, 0, 7, 0}, 7); 8. , 0. , , 7, (0: 4). sum = 7 7 - 7 = 0, 3, . - 0. 4. sum - k , count 4.

3rd: Integers .
I think you get the point;) This time, negative numbers can also increase some frequency. If we had a key sum - keyon the map, this means that between the previous sum ( sum - k) and now we had integers that were summed with k(call k + (sum - k) = sum- our current value). If so, let me increase the frequency count.