# Java Solution, PreSum + HashMap

• Solution 1. Brute force. We just need two loops (i, j) and test if `SUM[i, j]` = k. Time complexity O(n^2), Space complexity O(1). I bet this solution will TLE.

Solution 2. From solution 1, we know the key to solve this problem is `SUM[i, j]`. So if we know `SUM[0, i - 1]` and `SUM[0, j]`, then we can easily get `SUM[i, j]`. To achieve this, we just need to go through the array, calculate the current sum and save number of all seen `PreSum` to a HashMap. Time complexity O(n), Space complexity O(n).

``````public class Solution {
public int subarraySum(int[] nums, int k) {
int sum = 0, result = 0;
Map<Integer, Integer> preSum = new HashMap<>();
preSum.put(0, 1);

for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (preSum.containsKey(sum - k)) {
result += preSum.get(sum - k);
}
preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
}

return result;
}
}
``````

• @shawngao

Very elegant answer. Thank you for sharing. The if block can also be removed. :)

``````public class Solution {
public int subarraySum(int[] nums, int k) {
int sum = 0, result = 0;
Map<Integer, Integer> preSum = new HashMap<>();
preSum.put(0, 1);

for (int num : nums) {
sum += num;
result += preSum.getOrDefault(sum - k, 0);
preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
}
return result;
}
}
``````

• Python version.

``````class Solution(object):
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
d = {0: 1}
n = 0
s = 0
for i in range(len(nums)):
s += nums[i]
n += d.get(s - k, 0)
d[s] = d.get(s, 0) + 1
return n``````

• You can use the build-in merge method.

``````public int subarraySum(int[] nums, int k) {
int res = 0, sum = 0, l = nums.length;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int i = 0; i < l; res += map.getOrDefault((sum += nums[i++]) - k, 0), map.merge(sum, 1, Integer::sum));
return res;
}``````

• This post is deleted!

• No, the PreSum doesn't get TLE for now, and it's indeed very slow. :)

• No need to put(0, 1) this way.

``````        int ans = 0, sum = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(-sum, map.getOrDefault(-sum, 0) + 1);
sum += num;
ans += map.getOrDefault(k - sum, 0);
}
return ans;
``````

• why `sum-k`?

• This post is deleted!

• @apt275 sum - k means the array elements in between add up to k

• Why I change the order of put and if, the code will be wrong? Since the case of k = 0?

• @shawngao Two qq

• In what way does it check if the subarray is continuous?
• You say, "from solution 1" - how could you deduce solution 2 from solution 1? I mean to ask, how do we get `SUM[i,j]` if we know `SUM[0,i-1]` and `SUM[0,j]`?

• @shawngao You store the `sum` and the `number` of times you encountered this sum (by doing `preSum.getOrDefault(sum, 0) + 1`) in a map - could you kindly explain why? How is the number of times useful here...

• @BatCoder
the frequency is needed here because you need to add that to the result. Each time you find a sum that the hash map contains
`(sum - k)`, this means `(sum - k)` is a PreSum for a array some previous elements, and there could be more than one of them, so use `result += preSum.get(sum - k)` instead of `result++`.

• @pumpkin3
Thank you. I got it somewhat. Could you kindly explain the entire code please?

• @BatCoder
`sum` is the presum for first `i+1` numbers in the array, for example, sum of first 1 number is nums[0].
`preSum.put(0,1);` because the sum of first 0 number is 0 and this is an empty array`[]`, which is also a subarray for `nums`. In other words, the number of time `sum = 0` exists is 1.
then we loop through the array, calculate the presum for first `i+1` number and check if the map contains key `(sum - k)` , if it is, we increase the result by the number of `(sum - k)` we get from hash map.
We also need to put all `sum` in the map, that's what this line of code does: `preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);`

• We also need to put all sum in the map, that's what this line of code does: preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);

@pumpkin3
Okay, so I got your point. We are storing `<sum, frequency of this sum>` in the map. Then we navigate through the input array, calculating the `sum` and checking if its complement (`sum-k`) exists in the map. If it does, then we simply update the counter variable (`result`); if not, then we capture this `sum` and its frequency in the map. Is my understanding correct?

And one qq - we check for the complement `sum-k` in the map, so doesn't it make sense to store the complement (rather than the `sum`) in the map?

• @BatCoder
yes you understand it almost correctly.
One thing to know is that no matter the complement `(sum - k)` exits or not, we always need to increase the frequency of the `sum` in the map.

As for your question, we need to find the number of subarrays that whose sum equals `k`. To compute the sum of an subarray, it is useful to use preSum. For example, given an array`nums = [-3, 1, 2, -3, 5]`, its preSum is `preSum = [0, -3, -2, 0, -3, 2]`. Let's say we want to calculate the sum of subarray `nums[1,3] which is [1, 2, -3]`, it can be computed using preSum:
`preSum[4] - preSum[1] = -3 - (-3) = 0`.
If a subarray from i to j whose sum is `k`, it means `preSum[j+1] - preSum[i] = k`. So the complement `(sum - k`) equals another sum.

• @pumpkin3 Nice explanation. Thank you! :)

• Same idea..btw, brute force works fine this time.

``````    public int subarraySum(int[] nums, int k) {
int[] preSum = new int[nums.length];
preSum[0] = nums[0];
for (int i = 1; i < nums.length; i++) preSum[i] = preSum[i - 1] + nums[i];
int result = 0;
for (int i = 0; i < preSum.length; i++) {
if (preSum[i] == k) result++;
for (int j = i + 1; j < preSum.length; j++) {
if (preSum[j] - preSum[i] == k) result++;
}
}
return result;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.