Subarray Sum Equals K LeetCode Solution

LeetCode LeetCodeSolutions tiktok

Problem Statement

The Subarray Sum Equals K LeetCode Solution – “Subarray Sum Equals K” states that you are given an array of integers “nums” and an integer ‘k’, return the total number of continuous subarrays whose sum equals to ‘k’.

Example: nums = [1, 2, 3],
k=3
2

Explanation:

There are two subarrays whose sum is 3:

• First from index 0 to 1 i.e. [1, 2],
• Second from index 2 to 2 i.e. 
nums = [1, 1, 1],
k=3
2

Explanation:

There are two subarrays whose sum is 2:

• First from index 0 to 1 i.e. [1, 1],
• Second from index 1 to 2 i.e. [1, 1]

Approach

Idea:

The main idea is to use a hash map to store the frequency of prefix sums.

So, we’ll iterate over the array, finding how many subarrays exist whose sum equals k and ends at the current point on each iteration.

So, if the value of the prefix sum up to this point is ‘prefixSum,’ the next step is to determine how many prefix sums exist whose value is (prefixSum – k). It can be found in O(1) by using the hash map, which stores the frequency of prefix sums.

Code

C++ Program of Subarray Sum Equals K:

#include <bits/stdc++.h>
using namespace std;
int subarraySum(vector<int> &nums, int k)
{
int n = nums.size();
unordered_map<int, int> prefixSumsFrequency;
prefixSumsFrequency = 1;
int prefixSum = 0;
for (int i = 0; i < n; i++)
{
prefixSum += nums[i];
prefixSumsFrequency[prefixSum]++;
}
}
int main()
{
vector<int> nums = {1, 2, 3};
int k = 3;
cout << subarraySum(nums, k);
return 0;
}
2

JAVA Program of Subarray Sum Equals K:

import java.util.*;

public class TutorialCup {
public static int subarraySum(int[] nums, int k) {
int answer = 0, prefixSum = 0;
Map<Integer, Integer> prefixSumsFrequency = new HashMap<>();
prefixSumsFrequency.put(0, 1);
for (int i = 0; i < nums.length; i++) {
prefixSum += nums[i];
answer += prefixSumsFrequency.getOrDefault(prefixSum - k, 0);
prefixSumsFrequency.put(prefixSum, prefixSumsFrequency.getOrDefault(prefixSum, 0) + 1);
}
}

public static void main(String[] args) {
int[] nums = { 1, 2, 3 };
int k = 3;
System.out.println(subarraySum(nums, k));
}
}
2

Complexity Analysis for Subarray Sum Equals K LeetCode Solution

Time Complexity

The time complexity of the above code is O(n) because we are traversing the array only once.