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 1:
Note:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
Solution
Here we can take advantage of the Prefix Sum of the given array, Maintain prefix sum and check if
Code
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
import java.util.HashMap; import java.util.Map; public class SubArraySumK { public static void main(String[] args) { int [] a= {1,1,1}; int k=2; System.out.println(new SubArraySumK().subarraySum(a, k)); } public int subarraySum(int[] nums, int k) { int sum = 0, result = 0; Map<Integer, Integer> preSum = new HashMap<>(); // Maintains prefixSum and count of subArray ending with sum as k. preSum.put(0, 1); for (int i = 0; i < nums.length; i++) { sum += nums[i]; if (preSum.containsKey(sum - k)) { result += preSum.get(sum - k); } preSum.put(sum, preSum.getOrDefault(sum, 0) + 1); } return result; } } |
Output
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.