DevExCode

LeetCode 560: Subarray Sum Equals K Solution

Master LeetCode problem 560 (Subarray Sum Equals K), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

560. Subarray Sum Equals K

Medium
ArrayHash TablePrefix Sum

Problem Explanation

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.

:

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 560 (Subarray Sum Equals K)?

This page provides optimized solutions for LeetCode problem 560 (Subarray Sum Equals K) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 560 (Subarray Sum Equals K)?

The time complexity for LeetCode 560 (Subarray Sum Equals K) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 560 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 560 in Java, C++, or Python.

Back to LeetCode Solutions