Subarray Sum Equals K Leetcode Solution
Subarray Sum Equals K Leetcode Problem :
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
Subarray Sum Equals K Leetcode Solution :
Constraints :
- 1 <= nums.length <= 2 * 104
- -1000 <= nums[i] <= 1000
- -107 <= k <= 107
Example 1:
- Input: nums = [1,2,3], k = 3
- Output: 2
Approach :
The solution uses a hash table to store the cumulative sum of the array up to each index, along with the number of times that sum has occurred. The algorithm works as follows:
Initialize a hash table map to store the cumulative sum of the array up to each index, along with the number of times that sum has occurred.
Initialize a variable count to store the number of subarrays with sum k.
Iterate over the array, starting at index 0.
Add the current element to the cumulative sum.
If the cumulative sum is equal to k, increment count.
If the cumulative sum minus k is present in the hash table, increment count by the number of times that sum has occurred.
Add the current cumulative sum to the hash table, along with the number of times that sum has occurred.
Return count.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int subarraySum(vector< int>& nums, int k) {
int n = nums.size();
int count =0,sum =0;
unordered_map< int,int> map;
for(int i=0;i< n;i++){
sum = sum + nums[i];
if(sum == k){
count ++;
}if(map.find(sum - k) != map.end()){
count = count +map[sum-k];
}
map[sum]++;
}
return count;
}
};
class Solution {
public int subarraySum(int[] nums, int k) {
int sum = 0;
int ans = 0;
HashMap< Integer,Integer> map = new HashMap<>();
map.put(0,1);
for(int j=0;j< nums.length;j++){
sum += nums[j];
if(map.containsKey(sum -k)){
ans += map.get(sum-k);
}
map.put(sum,map.getOrDefault(sum,0)+1);
}
return ans;
}
}
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
result = 0
prefix_sum = 0
d = {0 : 1}
for num in nums:
prefix_sum = prefix_sum + num
if prefix_sum - k in d:
result = result + d[prefix_sum - k]
if prefix_sum not in d:
d[prefix_sum] = 1
else:
d[prefix_sum] = d[prefix_sum] + 1
return result
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment