algoadvance

Leetcode 560. Subarray Sum Equals K

Problem Statement

Given an array of integers nums and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Clarifying Questions

  1. Can the array contain negative numbers? Yes.
  2. Are the elements in the array necessarily integers? Yes.
  3. Is the array guaranteed to be non-empty? Yes, per the problem description.
  4. Should the subarrays be of at least length 1? Yes, subarrays need to be non-empty continuous parts of the original array.

Strategy

To solve the problem, we can use a hashmap (unordered_map in C++) to keep track of the cumulative sums and their frequencies. This will help us efficiently calculate the number of subarrays that sum up to k.

Here is the step-by-step approach:

  1. Initialize a hashmap to store the cumulative sum and its frequency.
  2. Initialize sum to 0, which will keep track of the cumulative sum while iterating through the array.
  3. Initialize count to 0, which will store the count of subarrays that sum to k.
  4. Iterate over the elements of the array, updating the cumulative sum.
  5. For each element, check if the cumulative sum minus k exists in the hashmap. If it does, it means there is a subarray ending at the current index with a sum of k.
  6. Update the hashmap with the current cumulative sum.
  7. Return the count of subarrays that sum to k.

Code

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> cumulativeSumFreq; // To store cumulative sum and its frequency
        cumulativeSumFreq[0] = 1; // To account for subarrays that begin at the start of the array
        int sum = 0;
        int count = 0;

        for (const int& num : nums) {
            sum += num;
            
            // Check if there is a subarray summing to k
            if (cumulativeSumFreq.find(sum - k) != cumulativeSumFreq.end()) {
                count += cumulativeSumFreq[sum - k];
            }

            // Update the frequency of the current cumulative sum
            cumulativeSumFreq[sum]++;
        }

        return count;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1, 1, 1};
    int k = 2;
    cout << sol.subarraySum(nums, k) << endl; // Output: 2
    return 0;
}

Time Complexity

This approach captures the essence of leveraging prefix sums and hash maps to maintain constant look-up times, resulting in a highly efficient solution.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI