/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
const subarraySum = function (nums, k) {
let res = 0;
let dp = [];
for (let i = 0, ii = nums.length; i < ii; ++i) {
dp[i] = [];
dp[i][i] = nums[i];
if (nums[i] === k) {
++res;
}
}
for (let i = 1, ii = nums.length; i < ii; ++i) {
for (let j = 0; j < i; ++j) {
dp[j][i] = dp[j][i - 1] + nums[i]
if (dp[j][i] === k) {
++res;
}
}
}
console.log(res);
return res;
};
const subarraySum1 = function (nums, k) {
/*
1. HashhashMap<sum[0,i - 1], frequency>
2. sum[i, j] = sum[0, j] - sum[0, i - 1] --> sum[0, i - 1] = sum[0, j] - sum[i, j]
k sum hashhashMap-key --> hashhashMap-key = sum - k
3. now, we have k and sum.
As long as we can find a sum[0, i - 1], we then get a valid subarray
which is as long as we have the hashhashMap-key, we then get a valid subarray
4. Why don't hashMap.put(sum[0, i - 1], 1) every time ?
if all numbers are positive, this is fine
if there exists negative number, there could be preSum frequency > 1
*/
let res = 0, sum = 0;
let hashMap = {}
hashMap[0] = 1;
for (let i = 0, ii = nums.length; i < ii; ++i) {
sum += nums[i];
if (hashMap[sum - k]) {
res += hashMap[sum - k];
}
hashMap[sum] = (hashMap[sum] ? hashMap[sum] : 0) + 1
}
return res;
};
subarraySum([1, 1, 1], 2)
subarraySum([1, 2, 3], 3)