Subarray Sum Equals K | Leet Code Subarray Sum Equals K

“Subarray Sum Equals K” is a problem often encountered in computer programming and deals with arrays, which are simply lists of numbers. This problem is about finding how many subarrays (contiguous portions of the array) have a sum equal to a specific target number, K.

Let’s break it down with an example:

Problem: Given an array [1, 2, 3, 4, 5] and a target sum K = 7, how many subarrays have a sum equal to K?

Solution: We need to find the subarrays where the sum of their elements is equal to K = 7.

1. Subarray: [1, 2, 3, 4] → Sum: 1 + 2 + 3 + 4 = 10 (not equal to K)
2. Subarray: [2, 3, 4] → Sum: 2 + 3 + 4 = 9 (not equal to K)
3. Subarray: [3, 4] → Sum: 3 + 4 = 7 (equal to K)
4. Subarray: [4, 5] → Sum: 4 + 5 = 9 (not equal to K)
5. Subarray: [5] → Sum: 5 (not equal to K)

In this example, there is one subarray [3, 4] that has a sum equal to the target K = 7.

This problem can be trickier with larger arrays and larger target sums. The idea is to keep track of the running sum as you iterate through the array. This helps in counting the number of subarrays that have the desired sum.

Remember that subarrays are always contiguous portions of the array, meaning the elements should be consecutive in the original order.

“Subarray Sum Equals K” problem is about finding and counting subarrays with a specific sum in an array of numbers.

Here’s how you can implement the solution to the “Subarray Sum Equals K” problem in both Java and Python.

Java:

import java.util.HashMap;

public class SubarraySumEqualsK {
    public static int subarraySum(int[] nums, int k) {
        int count = 0;
        int sum = 0;
        HashMap<Integer, Integer> sumFreq = new HashMap<>();
        sumFreq.put(0, 1); // Initialize with sum 0 frequency 1

        for (int num : nums) {
            sum += num;
            if (sumFreq.containsKey(sum - k)) {
                count += sumFreq.get(sum - k);
            }
            sumFreq.put(sum, sumFreq.getOrDefault(sum, 0) + 1);
        }

        return count;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int k = 7;
        System.out.println("Number of subarrays with sum " + k + ": " + subarraySum(nums, k));
    }
}

Python:

def subarraySum(nums, k):
    count = 0
    sum = 0
    sum_freq = {0: 1}  # Initialize with sum 0 frequency 1

    for num in nums:
        sum += num
        if sum - k in sum_freq:
            count += sum_freq[sum - k]
        sum_freq[sum] = sum_freq.get(sum, 0) + 1

    return count

nums = [1, 2, 3, 4, 5]
k = 7
print("Number of subarrays with sum", k, ":", subarraySum(nums, k))

Both the Java and Python implementations use a hashmap (or dictionary) to keep track of the frequencies of sums encountered. This allows them to efficiently count the number of subarrays with the desired sum. The logic remains the same in both languages, even though the syntax differs.

Thank You!