Leet Code 560. Subarray Sum Equals K — Explained Python3 Solution
Problem Description
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 1:
Input:nums = [2,2,3,0,4,-1,1,6], k = 7
Output: 3Solution
Obvious Solution
There is certainly a brute force way. Iterarte the whole list, check the sum of (currentElement to currentElement+1), (currentElement to currentElement + 2), pesudo code looks like:
In total, there are 3 loops and make the time complexity O(N³). It should work but definitely not an efficient way. There are ways to optimize this since there are many duplication of computation and the complexity can be decreased to O(N²).
Best Solution (to me)
Obviously, each subarray will end up with some index. Let me use i to represent that some index. And sum(0 to i) is very easy (and cheap — just take O(N)) to get.
Look at below example at i = 4, sum(0 to 4)= X + K. That means sum(0 to 4) can be broken to 2 parts, the second part is what I desire(with the sum of K), the first part X is actaully another sum which accumulate from 0 to 1. Now there is some light: if I have sum(0 to i), I can assume there is an index j (where j<i) , check if sum(0 to i) - K occurs in previous sum(0 to 0), sum(0 to 1), sum(0 to 2)…sum(0 to i-1), and increase the counter when an occurance is found. The value of the counter is the number of subarrays ending with index i that qualify the sume of K. In below example for index = 4, only sum(0 to 1) + K = sum(0 to 4), then there is only 1 qualified subarray which is [3,0,4].
Please note that in some case, there could be more than 1 qualified subarray.
Again look into another example as followed. For subarrays that ending at index 5, there are 2 cases:
sum(0 to 2) + sum(3 to 5)
sum(0 to 1) + sum(2 to 5)
And sum(0 to 2) and sum(0 to 1) are equal (both to 0).
Therefore, I need a Hashmap to record all sum(0 to x) (as the key) and its occurance (as the value). When I have sum(0 to i), I can check in the hasmap the value of sum(0 to i)-K to get the occurance number, and that number will the subarrays that ending with index i.
There is one trick however, again with my first example, what if sum(0 to i) itself is already equal to K like below the qualified subarray [2,2,3]? At this moment, the breakdown is : sum(0 to 2) = 0 + sum(0 to 2). The trick I play is add {0:1} to the hashmap saying for sum of 0, there is by default 1 occurance.
Alright, now here comes the code.
Time & Space Complexity
As above illustration/code shows, the time complexity is O(N): it just goes through each element in the input array for once only and with the loop each operation is O(1).
When it comes to space complexity: there is a hashmap which can scale (in worse case) with the size of input array, so it can take up to O(N) space and hence the space complexity is O(N).
Python 3 knowledge points
Within the solution, hashmap is used. I put together a post Python Cheatsheet with a section hashmap. Click https://medium.com/@edward.zhou/python3-cheatsheet-continuously-updated-66d652115549 to view more cheats :)
Extended Reading/Thinking
What if you are asked to return all subarrays?
