查找和等于指定数字的所有子数组？JavaScript（滑动窗口算法）

给定一个数字数组和一个数字，我们的任务是编写一个函数，返回所有加起来等于第二个参数提供的数字的子数组。

例如：

const arr = [23, 5, 1, 34, 12, 67, 9, 31, 6, 7, 27];
const sum = 40;
console.log(requiredSum(arr, sum));

应该输出以下数组：

[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]

因为这三个子数组都加起来等于 40。

滑动窗口算法（线性时间）

此算法主要用于需要在数组中查找子数组/字符串中查找满足特定条件的子字符串时。而这个问题正是滑动窗口算法的理想选择。

滑动窗口算法正如其名称所示，我们创建一个窗口，它只是原始数组的一个子数组。此窗口试图通过增加或减小来获得稳定性。

稳定性是指问题中指定的条件（例如，此处加起来等于特定数字）。一旦它变得稳定，我们就记录窗口并继续滑动它。通常，在 90% 的问题中，我们从左侧开始窗口，并一直滑动它，直到它的末端到达数组/字符串的末端。

让我们来看一下代码，以便更熟悉滑动窗口算法。

示例

const arr = [23, 5, 1, 34, 12, 67, 9, 31, 6, 7, 27];
const sum = 40;
const findSub = (arr, sum) => {
   const required = [];
   for(let start = 0, end = 0, s = 0; end <= arr.length || s > sum ; ){
      if(s < sum){
         s += arr[end];
         end++;
      }else if(s > sum){
         s -= arr[start];
         start++;
      }else{
         required.push(arr.slice(start, end));
         s -= arr[start];
         s += arr[end];
         start++;
         end++;
      };
   };
   return required;
};
console.log(findSub(arr, sum));

start 和 end 变量表示窗口在不同点的起始和结束位置。

最初两者都从 0 开始，然后如果所需总和小于给定总和，则增加窗口大小；如果大于给定总和，则减小窗口大小；如果在任何时候两者都相等，则将该子数组推入所需数组中。然后将窗口向右移动一个单位距离。

输出

此代码在控制台中的输出将为：

[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]

AmitDiwan

更新于：2020 年 8 月 20 日

441 次浏览

启动您的职业生涯

完成课程获得认证

开始