Subarray Sum Equals K - Leetcode Solution

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).

1