LeetCode 560. Subarray Sum Equals K Explanation and Solution

Показать описание

Thanks in advance. :D

Happy coding every day!

Рекомендации по теме

Комментарии

Here is the approach : ( you might find it helpful)

Say you are given an array e.g. [a0, a1, a2, a3, a4, a5, a6... an] .

[a0, a1, a2, a3, a4, a5, a6, ... an]
^ ^
sumI sumJ

sumI = sum of numbers till a2 (a0 + a1 + a2)
sumJ = sum of numbers till a5 (a0 + a1 + a2 + a3 + a4 + a5)

Now lets say the difference between sumJ and sumI is equal to k.
What that means is, the sum of numbers between a2 and a5 is equal to k ( a3 + a4 + a5 = k ), which means we found a subarray whose sum is equal to k.

We can write a3 + a4 + a5 = k as sumJ - sumI = k and sumJ - sumI = k can be written as sumJ - k = sumI

The expression sumJ - k = sumI, means have we already seen a sum which is equal to sum at current index j minus k. If yes, it means we found a subarray whose sum is equal to k.

And we keep track of how many times we see a particular sum using a HashMap.

Code :
class Solution {
public int subarraySum(int[] nums, int k) {
if(nums == null || nums.length == 0)
return 0;
int count = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0;
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;
}
}

alammahtab

Your videos are very helpful, Thank you!

bushnam

Why do we want to find (sum-k) in our hash table?

corporalwaffles

Awesome video, very helpful, thank you! Just wondering, why is it *res += map.get(sum - k)* and not *res++* ? When we find a new subarray, why wouldn’t we increment the count by 1?

Joy-ygnl

Generally I watch tutorial videos in 1.5x, I had to watch this in 0.5x, but still I didn't understand that well, I'm too dumb

unav-daily

your solution desn't work in all cases. Try [1, 2, 0] k=3 or [1, 0, 1] k=1

daniel

LeetCode 560. Subarray Sum Equals K Explanation and Solution

Subarray Sum Equals K - Prefix Sums - Leetcode 560 - Python

LeetCode 560 | Subarray Sum Equals K | Solution Explained (Java + Whiteboard)

Subarray Sum Equals K | Prefix Sums | Leetcode 560 | Animation | Intuition

LeetCode Subarray Sum Equals K Solution Explained - Java

Subarray sum equals K | Number of subarrays with sum equals K | Leetcode #560

Subarray Sum Equals K - LeetCode 560 - Coding Interview Questions

Meta Coding Interview - Subarray Sum Equals K - Leetcode 560

SUBARRAY SUM EQUALS K | LEETCODE 560 | PYTHON SOLUTION

Subarray Sum Equals K | Intuitive Explanation + Code (LeetCode 560)

LeetCode Day 22 - Subarray Sum Equals K

leetcode 560. #shorts Maximum Size Subarray Sum Equals k

Leetcode 560. Subarray Sum Equals K

Leetcode 560 - Subarray Sum Equals K (JAVA Solution Explained!)

Subarray Sum Equals K - 560. LeetCode - Java

Subarray Sum Equals K - LeetCode 560 - Python

25. Subarray Sum Equals K | Leetcode 560 | Array | Prefix Sum

560. Subarray Sum Equals K(Leetcode Solution)

Count Subarray sum Equals K | Brute - Better -Optimal

Google Coding Interview Question - Leetcode 560. Subarray Sum Equals K

560. Subarray Sum Equals K - Day 10/28 Leetcode February Challenge

LeetCode 560. Subarray Sum Equals K Explanation and Solution

[SOLVED!] Subarray Sum Equals K - LeetCode 560 - Java

LeetCode - 560. Subarray Sum Equals K | Prefix sum | Java

Subarray Sum Equals K | LeetCode 560 | Coders Camp