/**
 * @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)