[数据结构与算法][JavaScript 刷题] 哈希表 - 和为 K 的子数组 leetcode 560

[JavaScript 刷题] 哈希表 - 和为 K 的子数组, leetcode 560

github repo 地址: https://github.com/GoldenaArcher/js_leetcode，Github 的目录 大概 会更新的更勤快一些。

题目地址：560. Subarray Sum Equals K

题目

如下：

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

解题思路

暴力解

这个解法会超时，但是我觉得这个解法说的还是挺清楚的，还给了一个比较好的初始思路。

这种将所有的前置和存储在一个数组中，然后遍历两边前置去计算有多少个子数组。

以 [1, 2, 3] 为例，前置和数组的值为：[ 0, 1, 3, 6 ]。

数组和的长度比数组多一个是当下标为 0 时，数组和自然为 0。

当下标为 1 时，当前值为 nums[0] + sums[0]。

当下标为 2 时，，当前值为 nums[1] + sums[1]。

以此类推。

总体上来说就是将所有的前置和相加，最后用进行双重遍历，找到 sums[i + j] - sums[i] === k 出现过多少次即可。

哈希表

哈希表的解法一定程度上来说是 2 sum 的变种，2 sum 在 map 中获取的是 $target?nums[i]$ 存储的键值对是 $(nums[i],i)$，这里获取的则是 $sum?k$，其中 $sum$ 为前数和，存储的键值对为 $(sum,map.get(sum)+1)$。

依旧以官方题目中的 nums = [1, 2, 3], k = 3 为例：

1. 初始化时

   map 的值为： { ( 0 , 1 ) } \{(0, 1)\} {(0,1)}，原因与暴力解中一样

2. 当下标为 0 时

   此时在 map 中搜索 $sum?k$，即 -2。map 中并不包含这个值，继续下一步操作

   map 的值为： { ( 0 , 1 ) , ( 1 , 1 ) } \{(0, 1), (1, 1)\} {(0,1),(1,1)}

3. 此时下标为 1

   此时在 map 中搜索 $sum?k$，即 0, map 中可以取得 $(0,1)$，所以 counter += map.get(sum - k)

   map 的值为： { ( 0 , 1 ) , ( 1 , 1 ) , ( 3 , 1 ) } \{(0, 1), (1, 1), (3, 1)\} {(0,1),(1,1),(3,1)}

   找到 $sum?k$ 即代表当前子数组肯定能找到这样的一个组合，也就是 [1, 2]

4. 此时下标为 2

   此时在 map 中搜索 $sum?k$，即 3, map 中可以取得 $(3,1)$，所以 counter += map.get(sum - k)

   map 的值为： { ( 0 , 1 ) , ( 1 , 1 ) , ( 3 , 1 ) , ( 6 , 1 ) } \{(0, 1), (1, 1), (3, 1), (6, 1)\} {(0,1),(1,1),(3,1),(6,1)}

最终获得结果为 2.

关于关于出现包含不止一个子数组的情况，可以参考 nums = [1,-1,0], k = 0 这个案例。

1. 初始化时

   map 的值为： { ( 0 , 1 ) } \{(0, 1)\} {(0,1)}

2. 当下标为 0

   此时在 map 中搜索 $sum?k$，即 -1。map 中并不包含这个值，继续下一步操作

   map 的值为： { ( 0 , 1 ) , ( 1 , 1 ) } \{(0, 1), (1, 1)\} {(0,1),(1,1)}

3. 当下标为 1

   此时在 map 中搜索 $sum?k$，为 0，map 中包含这个键，因此 counter += 1

   map 的值为： { ( 0 , 2 ) , ( 1 , 1 ) } \{(0, 2), (1, 1)\} {(0,2),(1,1)}

4. 当下标为 2

   此时在 map 中搜索 $sum?k$，为 0，map 中包含这个键，因此 counter += 1

   注意，这里会出现 2 是因为有两个数组可以实现当前值：

   1. [1, -1, 0]
   2. [0]

   map 的值为： { ( 0 , 3 ) , ( 1 , 1 ) } \{(0, 3), (1, 1)\} {(0,3),(1,1)}

使用 JavaScript 解题

暴力解法

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
  const n = nums.length;
  const sums = new Array(n + 1).fill(0);

  for (let i = 1; i <= n; i++) {
    sums[i] = sums[i - 1] + nums[i - 1];
  }

  let counter = 0;

  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      if (sums[j + 1] - sums[i] === k) counter++;
    }
  }

  return counter;
};

哈希表解法

var subarraySum = function (nums, k) {
  const map = new Map([[0, 1]]);

  let counter = 0,
    sum = 0;

  for (const num of nums) {
    sum += num;
    if (map.has(sum - k)) counter += map.get(sum - k);

    if (map.has(sum)) map.set(sum, map.get(sum) + 1);
    else map.set(sum, 1);
  }

  return counter;
};