时间戳

首页 > 解决方案 > JavaScript：返回总和等于 K 的所有连续子数组

javascript - JavaScript：返回总和等于 K 的所有连续子数组

问题描述

这是这个leetcode question的变体，但我们不想返回计数，而是希望返回实际的连续子数组。例如，如果num = [1,2,4,7] k=7返回值应该是[[1,2,4],[7]].

我使用哈希图来存储所有可能的索引的累积总和以及原始问题出现相同总和的次数，它要求返回count

var subarraySum = function(nums, k) {
  let sum = 0;
  let count = 0;
  const myMap = new Map();
  myMap.set(0, 1);

  for (let num of nums) {
    sum += num;
    count += myMap.get(sum - k) || 0;
    myMap.set(sum, (myMap.get(sum) || 0) + 1);
  }
  
  return count;
}

但我似乎无法弄清楚如何调整此解决方案以返回实际的子数组。

标签： javascriptalgorithm

解决方案

解决方案

要返回所有匹配的连续子数组，您应该myMap稍微不同地使用您的子数组。对于每个键sum，它应该存储索引，而不是 的频率sum。

此外，您ans应该包含一个匹配的连续子数组的数组，并且它会根据存储在myMap.

基本上，如果有索引sum - k，那么它们是新匹配子数组的开始索引，而当前索引i是结束索引。因此，您遍历所有起始索引并添加新的匹配子数组，如下所示：

...
    if (myMap.has(key)) {
      indices = myMap.get(key) 
      for (const index of indices) {
        matchingSubArrayIndices.push([index, i])    
      }
    } 
...

请在下面找到完整的代码：

var subarrays = function(nums, k) {
  let sum = 0;
  const myMap = new Map();
  
  myMap.set(0, [0]);
  const matchingSubArrayIndices = new Array()

  for (var i = 0; i < nums.length; i++) {
    num = nums[i]
    sum += num;
    let key = sum - k
    if (myMap.has(key)) {
      indices = myMap.get(key) 
      for (const index of indices) {
        matchingSubArrayIndices.push([index, i])    
      }
    }
    
    array = myMap.get(sum)
    if (array == undefined) {
      array = new Array() 
    }
    array.push(i + 1)
    myMap.set(sum, array);
  }
  
  for (let indices of matchingSubArrayIndices) {
    console.log("Matching subarray")
    for (i = indices[0]; i <= indices[1]; i++) {
        console.log(nums[i] + " ")
    }
  }
}

subarrays([1,3,4], 4)

该解决方案对于大多数输入都非常有效，但对于如下输入：

0 0 0 0
0

它将在时间和空间上是二次的，因为在每次迭代中，matchingSubArrayIndices它都会线性增长，因此对于所有迭代，它都是二次的。

结论

即使算法在最坏的情况下是二次的，但这不是算法本身的问题，而是输出的问题。如果输出是二次的，那么任何解都至少是二次的。

推荐阅读