資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究JavaScript 中線性時間複雜度的兩數之和問題
問題陳述要求在 JavaScript 中以線性時間執行兩數之和問題。它定義並探討了各種演算法，這些演算法可以幫助我們在 JavaScript 中給定的源資料中找到存在的最小公因數。
什麼是 JavaScript 中的兩數之和問題？
JavaScript 中的兩數之和問題等同於找到給定輸入數字陣列中的一對索引，該索引加起來等於目標和，目標和也由使用者作為輸入提供。
給定一個整數陣列和目標和，我們將遍歷數字陣列以找出數字對，可能存在一個或多個數字對加起來等於作為輸入源提供的目標值。找到數字對後，我們可以查詢它們的索引以完整地解決問題陳述。
這裡的小技巧是陣列中的每個輸入值只能使用一次，並且您不能重複使用相同的元素進行求和，其中結果對可以按任意順序返回。
示例
問題陳述的視覺示例如下所示
const arr = [ 2 ,5 ,9 ,7 ,3 , 8 , 1 ]; const targetSum = 10 ;
輸出
[ 0, 5 ] = arr[0] + arr[5] [ 2, 6 ] = arr[2] + arr[6] [ 3, 4 ] = arr[3] + arr[4]
在這裡，我們透過掃描整個陣列來以程式設計方式匹配對，以將陣列中存在的每個元素與陣列中存在的其他不同元素進行比較，因為不允許您已經選擇或選擇的特定元素的重複或重複再次成為對的成員之一，這違反了問題陳述中已經提到的兩數之和問題的規則。
演算法 - 使用迴圈
步驟 1：宣告一個名為 twoSumProblem 的函式，該函式接收數字陣列的輸入，該陣列將作為查詢索引對的主要輸入源以滿足目標和，加上目標和值，目標和值也將由使用者給出，因為要查詢的索引對高度依賴於所需的和值。
步驟 2：在給定的函式中，我們使用了巢狀迴圈功能，其中外迴圈將選取索引對中的第一個數字，內迴圈將選取索引對中的第二個值，該值將使用 i 迴圈的 + 1 值向前移動以跟蹤和排列資料集域中的不同索引對。
步驟 3：現在將索引對的數量排列到比較功能中，以檢查排列的特定對的加法是否滿足目標和。
步驟 4：如果是，它將返回特定的索引作為元素的索引對，這些元素加起來等於使用者提供的 targetSum。
示例
function twoSumProblem ( arr , targetSum )
{
for(let i = 0; i<arr.length ; i++ )
{
for(let j = i+1 ; j<arr.length ; j++)
{
if(arr[i] + arr[j] === targetSum)
{
return [ i ,j ]
}
}
}
}
const arr = [ 2 ,5 ,9 ,7 ,3 , 8 ,1 ];
const pairOfIndices = twoSumProblem(arr , 10);
console.log(pairOfIndices);
輸出
[ 0, 5 ]
時間和空間複雜度
在上面的演算法和程式碼中，我們使用了巢狀迴圈，其中外迴圈將一直向前移動到數字陣列的長度，導致時間複雜度為 O(n)，內迴圈也一直向前移動到陣列的長度，導致時間複雜度也為 O(n)。由於內迴圈依賴於外迴圈進行遍歷，因此這兩個單獨的時間複雜度的乘積結果為 O(n) * O(n) = O(n^2) 作為其最壞情況下的時間複雜度。
空間複雜度為 O(1)，這意味著空間複雜度是恆定的，因為我們沒有分配任何額外的記憶體來解決問題。
我們可以以一種更有效的方式進一步最佳化 twoSumProblem，以犧牲空間複雜度為代價來降低時間複雜度。因為正如問題陳述中提到的，要線上性時間內找到兩數之和問題。
我們將使用雜湊表在 JavaScript 中以線性時間和空間複雜度來解決兩數之和問題。
什麼是 JavaScript 中的雜湊表？
JavaScript 中的雜湊表在幕後就像陣列一樣工作，它使用雜湊函式將標籤對映到陣列索引或索引。它是一種類似於陣列的資料結構，雜湊表具有使用鍵值對的雜湊表，其中雜湊鍵指的是陣列中的索引。
先前解決的演算法由於巢狀迴圈功能而導致時間複雜度最大，而雜湊表可以遍歷並找到任何內容，或者任何值的訪問速度為 O(1) 時間複雜度，這是最大的優勢。
演算法
該演算法將制定策略來迴圈陣列並僅遍歷陣列中存在的每個元素一次，並且必須有一些記憶體幫助來儲存在朝著目標和值的過程中獲得的索引。這裡的記憶體幫助器是雜湊表，其額外的記憶體分配丟棄了我們在 adobe 演算法中使用的第二個巢狀迴圈，並允許問題陳述線上性時間內解決。
步驟 1：宣告一個名為 newTwoSumProblem 的函式，該函式接收數字陣列和您要查詢索引對的目標和。
步驟 2：宣告一個新的雜湊表，並初始化為空值。
步驟 3：使用 for 迴圈遍歷陣列的長度，直到陣列的長度，並牢記是否有任何其他數字可以加到數字的當前值以實現目標和。
步驟 4：宣告並分配一個新的變數作為上面提到的額外記憶體，稱為 currentValue，它將在 for 迴圈的每次迭代中獲取 i 的當前值。
步驟 5：找到相對於當前值的索引對的下一個值，以便新值將根據使用 targetSum - currentValue 的雜湊函式需要多少值才能達到目標和來計算。
步驟 6：您使用雜湊表函式查詢索引對，其中當前值儲存在鍵值對模式中，其中鍵是實際值本身，值僅是該值的特定索引。
步驟 7：如果雜湊表中未找到當前值的配對，並且它等於 undefined，則雜湊表將再次開始使用 i 的下一個值查詢其補充索引對，以繼續處理其他數字陣列並重復相同的任務，直到您找到滿足目標和的索引對。
示例
function newTwoSumProblem (arr, targetSum) {
let hashMap = {};
for(let i = 0; i < arr.length; i++) {
const currentValue = arr[i];
if(hashMap[targetSum - currentValue] !== undefined)
{
return [hashMap[targetSum - currentValue], i];
}
hashMap[currentValue] = i;
}
return [];
}
const arr = [ 2 ,7 , 11, 15 ];
const pairOfIndices = newTwoSumProblem(arr , 9);
console.log(pairOfIndices);
稍後我們還可以使用上述主程式碼呼叫該函式，控制檯中的輸出將是
輸出
[0 , 1 ]
以下程式碼是人們在檢視問題陳述以獲得更好的空間和時間質量時可以想到的有效且最佳化的前向程式碼。
在上面的程式碼中，我們聲明瞭一個接收陣列輸入的函式。然後我們一步一步地進行，首先關注問題陳述的主要內容，即在數字陣列中找到任何其他數字，該數字可以加到當前數字以等於目標和值。
透過這種方式，我們可以從初始索引 0 開始迴圈，並嘗試查詢其他數字值，該值是透過使用 targetSum-currentValue 在雜湊表中查詢獲得的，如果它找不到當前值，則將當前值儲存在雜湊表中，使用鍵值對結構和 for 迴圈向前移動到索引值 1，並重復相同的過程，直到它找到滿足目標和的互補索引對。
時間和空間複雜度
這是一種有效的演算法，現在使用雜湊表，時間複雜度為 O(n)，空間複雜度也為 O(n)。因此它線上性時間內解決了問題陳述。
結論
這就是我們如何在編碼環境中邏輯上和有效地解決上述問題陳述的方式，將程式碼從巢狀迴圈更改為雜湊表功能，這使我們擁有巨大的能力來遍歷和執行操作，並在恆定的時間和空間複雜度內使用它。
2K+ 瀏覽量
