LeetCode 560: Subarray Sum Equals K

Explanation:

To solve this problem, we can use a HashMap to keep track of the cumulative sum of subarrays and their frequencies. By calculating the cumulative sum as we iterate through the array, we can check if there exists a subarray with sum k by checking if the difference between the current cumulative sum and k has been seen before. If it has, then there exists a subarray with sum k ending at the current index. We increment the count by the frequency of the cumulative sum difference.

Algorithm:

1. Initialize a HashMap to store cumulative sums and their frequencies. Also, initialize the count of subarrays with sum k and the cumulative sum to 0.
2. Iterate over the array:
   • Calculate the cumulative sum by adding the current element to the previous cumulative sum.
   • Check if the difference between the current cumulative sum and k has been seen before in the HashMap. If yes, increment the count by the frequency of that difference.
   • Update the frequency of the current cumulative sum in the HashMap.
3. Return the count of subarrays with sum k.

Time Complexity:

The time complexity of this approach is O(n), where n is the size of the input array.

Space Complexity:

The space complexity of this approach is O(n), where n is the size of the input array.

:

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