Problem statement:

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example:

Input:nums = [1,1,1], k = 2
Output: 2

Solution

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> preSum = new HashMap<>();
    preSum.put(0, 1); // we've seen sum 0 - once
    int sum = 0, count = 0;
    for(int i = 0; i < nums.length; i++) {
        sum += nums[i];
	**// if exsists sum - k, that means sum between those two points in array = k**
        if (preSum.containsKey(sum - k)) {
            count += preSum.get(sum - k);
        }
        preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
    }
    return count;
}

Time complexity:

O(n)

Space complexity:

O(n)

Approach:

if sum[i] - sum[j] == k, then sum of elements in between equal k; preSum hashmap sum → count