高效求解二和 II - 輸入數組已排序

「Two Sum II - 輸入陣列已排序」問題是一個經典的編碼挑戰，測試您對陣列和指標操作的理解。這也是展示優雅且高效的解決方案的絕佳機會。讓我們深入研究這個問題並分解解決它的最佳方法。

LeetCode 上的問題連結

問題陳述

給定一個按非遞減順序排序的 1 索引整數數組，您的目標是找到兩個數字，使其總和等於給定目標。您需要將這兩個數字的索引作為數組 [index1, index2] 返回，其中 1

約束條件

• 陣列編號依非遞減順序排序。
• 只有一個解。
• 同一個元素不能使用兩次。
• 輸入數組長度範圍為2到30,000。
• 數組中的值範圍從 -1000 到 1000。

輸入和輸出範例

1. 輸入： 數字 = [2,7,11,15]，目標 = 9
   
   輸出： [1, 2]

2. 輸入： 數字 = [2,3,4]，目標 = 6
   
   輸出： [1, 3]

3. 輸入： 數字 = [-1,0]，目標 = -1
   
   輸出： [1, 2]

方法：兩個指針

該問題的限制（排序數組和單一解決方案）使其成為兩指標技術的完美候選者。原因如下：

• 效率：兩個指標允許我們一次遍歷數組（O(n) 時間複雜度）。
• 恆定空間：我們避免使用輔助資料結構，遵循問題對恆定額外空間的要求。

執行

下面是兩個指標方法的 JavaScript 實作：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const length = nums.length;
    let rightPointer = length - 1;
    let leftPointer = 0;

    while (leftPointer < rightPointer) {
        if (nums[leftPointer] + nums[rightPointer] === target) {
            return [leftPointer + 1, rightPointer + 1];
        }
        if (nums[leftPointer] + nums[rightPointer] > target) {
            rightPointer--;
        } else {
            leftPointer++;
        }
    }
};

它是如何運作的

1. 初始化兩個指標：

   • leftPointer 從陣列的開頭開始。
   • rightPointer 從陣列結尾開始。

2. 迭代直到他們相遇：

   • 計算 leftPointer 和 rightPointer 處的元素總和。
   • 如果總和與目標匹配，則傳回 1 索引位置。
   • 如果總和大於目標，則遞減 rightPointer 以減少總和。
   • 如果總和小於目標，則增加 leftPointer 以增加總和。

3. 回索引：

   • 一旦找到正確的對，循環就會終止並返回索引。

範例演練

讓我們來看看第一個範例：

• 輸入： 數字 = [2, 7, 11, 15]，目標 = 9
• 初始化：左指標 = 0，右指標 = 3

迭代步驟：

1. 計算數字[0] 數字[3] = 2 15 = 17。
   • 太大，將 right 指標減為 2。
2. 計算數字[0] 數字[2] = 2 11 = 13。
   • 仍然太大，將 right 指標遞減到 1。
3. 計算數字[0] 數字[1] = 2 7 = 9。
   • 找到匹配項，回傳 [1, 2]。

重點

• 1 索引調整： 問題指定基於 1 的索引，因此我們在返回之前將兩個指標都加 1。
• 邊緣情況：約束保證了單一解決方案，因此我們不需要處理空數組或多個匹配。
• 最佳化： 使用兩指標方法確保我們滿足 O(n) 時間複雜度和恆定空間要求。

結論

兩指標方法透過利用輸入數組的排序性質，優雅地解決了「Two Sum II - 輸入數組已排序」問題。這是一種強大的技術，不僅可以確保效率，而且可以遵守空間限制，使其成為解決類似問題的首選方法。快樂編碼！

以上是高效求解二和 II - 輸入數組已排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！