資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學查詢和等於指定數字的所有子陣列？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 ] ]
更新於：2020 年 8 月 20 日
441 次瀏覽
廣告