LeetCode 167. 兩數之和 II - 輸入有序數組 | Python

文章目錄

• 167. 兩數之和 II - 輸入有序數組
• • 題目
  • 解題思路
  • 代碼實作
  • 實作結果
  • 歡迎關注

167. 兩數之和 II - 輸入有序數組

題目來源：力扣（LeetCode）

https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted

題目

給定一個已按照升序排列 的有序數組，找到兩個數使得它們相加之和等于目标數。

函數應該傳回這兩個下标值

index1

和

index2

，其中

index1

必須小于

index2

。

說明:

• 傳回的下标值（

  index1

  和

  index2

  ）不是從零開始的。
• 你可以假設每個輸入隻對應唯一的答案，而且你不可以重複使用相同的元素。

示例:

輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 2 與 7 之和等于目标數 9 。是以 index1 = 1, index2 = 2 。
           

解題思路

思路：雙指針

先審題，首先題目中所給的數組是有序的，因為這個前提，我們可以考慮使用雙指針的思路，縮小範圍，進而求得答案。

這裡，先注意題目中所給出的要求：

• 傳回的下标值，并不是從零開始，而是從 1 開始
• 題目有唯一解，是以求得答案可直接傳回。

現在說下算法的具體思路：

• 定義雙指針

  left, right

  ，分别指向有序數組的首尾；
• 令兩個指針所對應的數字相加，設為

  two_sum

  ，與

  target

  進行比較：
  • 若

    two_sum == target

    ，傳回

    [left + 1, right + 1]

    （因為傳回下标值從 1 開始）
  • 若

    two_sum > target

    ，則向前移動右指針；
  • 若

    two_sum < target

    ，則向後移動左指針。

算法實作的過程如下圖：

具體的代碼實作如下。

代碼實作

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        length = len(numbers)
        # 定義雙指針，分别指向數組首尾
        left = 0
        right = length - 1

        while left < right:
            # 令指針所對應的數字相加，與 target 作比較
            two_sum = numbers[left] + numbers[right]
            # 相等時，傳回索引值，因為下标從 1 開始計算，要相應 +1
            if two_sum == target:
                return [left + 1, right + 1]
            # 兩數之和大于 target，移動右指針縮小兩數和
            elif two_sum > target:
                right -= 1
            # 兩數和小于 target，移動左指針增大兩數和
            else:
                left += 1

        return None
           

實作結果

歡迎關注

公衆号 【書所集錄】