Leetcode 560 - Subarray Sum Equals K

Array

HashMap

Prefix Sum

Leetcode Link for Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= nums.length <= 2 * 10⁴

• -1000 <= nums[i] <= 1000

• -10⁷ <= k <= 10⁷

Solution:

public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> prefixSum = new HashMap<>();

        int count = 0;

        int sum = 0;

        prefixSum.put(0, 1);

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (prefixSum.containsKey(sum - k)) {
                count += prefixSum.get(sum - k);
            }
            prefixSum.put(sum, prefixSum.getOrDefault(sum, 0) + 1);
        }

        return count;

}

Github Link: https://github.com/miqbal3636/problem_solving/blob/main/src/com/spsoft/leetcode/medium/array/L560SubarraySumEqualsK.java

Explanation:

1. Initialization:

Create a HashMap object called prefixSum to store the cumulative sum and its frequency.

create Variable count to count valid subarrays and sum for the running sum.

prefixSum initially contains {0, 1} to handle cases where the subarray starts from index 0.

2. Iterate through nums:

For each element, add it to sum.

Check if (sum - k) exists in prefixSum. If it does, increment count by the frequency of (sum - k).

Update prefixSum to include the current sum and increment its frequency.

3. Return:

The final count of subarrays whose sum is equal to k.

Time Complexity: O(n), where n is the length of nums

Space Complexity: O(n) for HashMap

Author: Mohammad J Iqbal

Follow Mohammad J Iqbal on LinkedIn