Medium
跟之前做的一道two sum data structure design蛮像
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).
class Solution {
//< O(N^2)
public int subarraySum(int[] nums, int k) {
int count = 0;
int sum = 0;
Map<Integer, Integer> preSum = new HashMap<>();
preSum.put(0, 1);
//we want to know how many subarray exists such that s[i,j] == k
//s[i, j] = s[0, j] - s[0, i- 1]
//k = sum - s[0, i - 1]
for (int i = 0; i < nums.length; i++){
sum += nums[i];
count += preSum.getOrDefault(sum - k, 0);
preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
}
return count;
}
}
