查找总和等于数字的所有子数组？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 ] ]

因为这3个子阵列中的每一个加起来等于40。

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

当需要我们在满足特定条件的字符串中查找数组/子字符串中的子数组时，通常使用此算法。这个问题非常适合滑动窗口算法。

滑动窗口算法恰如其名，我们创建了一个窗口，该窗口不过是原始数组的子数组。该窗口试图通过增加或减少来获得稳定性。

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

让我们看一下使自己更熟悉滑动Windows算法的代码。

示例

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));

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

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

输出结果

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

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