Solution For Subarray Sum Equals K

Problem Statement:

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

Example:

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

Explanation:
The subarrays [1,1] and [2] have sum 2 and constitute the answer.

Solution:

The brute force approach for this problem takes O(n^2) time. We can loop through the array and for each element, we add the current element to the sum and check if the sum equals k. If the sum equals k, we increment the count of subarrays. We continue doing this until we reach the end of the array. This approach takes O(n^2) time because, in the worst case, we will iterate over all the subarrays.

A better approach is to use a HashMap to store the sum of all the elements up to the current index. We will iterate through the array and for each element, we will compute the sum up to that index and check if the difference between the current sum and k exists in the HashMap. If it exists, it means that the sum up to the current index minus the sum up to some previous index equals k. We increment the count of subarrays by the value of the sum difference in the HashMap. Finally, we update the value of the sum of the elements up to that index in the HashMap. If the sum doesn’t exist in the HashMap, we add the sum and its index to the HashMap.

Code:

Here is the Python code for the solution:

def subarraySum(nums, k):
sum_dict = {0:1}
count = 0
sum_ = 0
for i in range(len(nums)):
sum_ += nums[i] if sum_ – k in sum_dict:
count += sum_dict[sum_ – k] if sum_ in sum_dict:
sum_dict[sum_] += 1
else:
sum_dict[sum_] = 1
return count

Explanation of code:

1. We create an empty dictionary ‘sum_dict’ to store the sum of all the subarrays up to the current index and its frequency as key-value pairs.

2. We initialize the ‘count’ variable to 0 and the ‘sum_’ variable to 0. The ‘sum_’ variable stores the sum of all elements up to the current index.

3. We loop through the array, and for each element, we add it to the ‘sum_’ variable.

4. If the difference between the current sum and k exists in the ‘sum_dict’, we increment the ‘count’ variable by the value of that key in the dictionary. For example, if the value of the key sum_-k in ‘sum_dict’ is 2, it means that there are two subarrays whose sum is k.

5. If the current sum exists in the ‘sum_dict’, we increment the value of that key in the dictionary by 1. If it doesn’t exist, we add the current sum and its frequency as a key-value pair in the dictionary.

6. Finally, we return the value of the ‘count’ variable, which stores the total number of subarrays whose sum equals k.

Complexity Analysis:

Time complexity: O(n), where n is the length of the input array. We iterate through the array once.

Space complexity: O(n), where n is the length of the input array. We store the sum of the subarrays and their frequency as key-value pairs in a dictionary. In the worst case, all the elements in the array can be distinct. Therefore, the space complexity is O(n).

Step by Step Implementation For Subarray Sum Equals K

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

def subarraySum(nums, k):
        count = 0
        for i in range(len(nums)):
            sum = 0
            for j in range(i, len(nums)):
                sum += nums[j]
                if sum == k:
                    count += 1
        return count

var subarraySum = function(nums, k) {
    let sum = 0;
    let count = 0;
    let map = {0:1};
    
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (map[sum-k]) {
            count += map[sum-k];
        }
        map[sum] = (map[sum] || 0) + 1;
    }
    
    return count;
};

class Solution {
public:
    int subarraySum(vector& nums, int k) {
        int count = 0, n = nums.size(); 
  
        // Pick a starting point 
        for (int i = 0; i < n; i++) 
        { 
            // Initialize sum of current subarray 
            int sum = nums[i]; 
  
            // Try different end points for current 
            // subarray nums[i..j] 
            for (int j = i + 1; j <= n; j++) 
            { 
                // If sum equals k, then increment 
                // count 
                if (sum == k) 
                    count++; 
  
                // Add this element to the sum 
                if (j < n) 
                    sum += nums[j]; 
            } 
        } 
        return count; 
    }
};

public int SubarraySum(int[] nums, int k) { // edge case if (nums.Length == 0) return 0; // create a hashmap to store the sum of all elements up to the current index as the key, // and the number of times this sum has been seen as the value HashMap map = new HashMap(); // initialize the map with the default case where the sum is 0, which has been seen once map.Add(0, 1); // initialize a running sum and a count of the number of subarrays with sum k int sum = 0; int count = 0; // iterate through the array for (int i = 0; i < nums.Length; i++) { // add the current element to the running sum sum += nums[i]; // check if the map contains the key sum - k // if it does, that means we have found a subarray with sum k, // so we add the number of times this sum has been seen to our count if (map.ContainsKey(sum - k)) { count += map[sum - k]; } // add the current sum to the map or increment the value if it already exists if (map.ContainsKey(sum)) { map[sum]++; } else { map.Add(sum, 1); } } // return the count return count; }