查找所有和等于数字的子数组?JavaScript(滑动窗口算法)
javascriptweb developmentobject oriented programming更新于 2025/9/28 15:40:17
我们得到一个数字数组和一个数字；我们的工作是编写一个函数，返回所有子数组的数组，这些子数组的总和等于作为第二个参数提供的数字。
例如 −
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% 的问题中，我们从左边开始窗口并继续滑动它，直到它的末端到达数组/字符串的末尾。
让我们看一下代码，让我们更熟悉滑动窗口算法。
示例
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 ] ]
相关文章
有用资源
javascript 参考教程 - 该教程包含有关 javascript 的更多信息:https://www.cainiaomax.com/javascript/
