167. 兩數(shù)之和 II - 輸入有序數(shù)組

題目來源：力扣（LeetCode）
https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted

題目

給定一個(gè)已按照升序排列 的有序數(shù)組，找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)。

函數(shù)應(yīng)該返回這兩個(gè)下標(biāo)值 index1 和 index2，其中 index1 必須小于 index2。

說明:

• 返回的下標(biāo)值（index1 和 index2）不是從零開始的。
• 你可以假設(shè)每個(gè)輸入只對應(yīng)唯一的答案，而且你不可以重復(fù)使用相同的元素。

示例:

輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 2 與 7 之和等于目標(biāo)數(shù) 9 。因此 index1 = 1, index2 = 2 。

解題思路

思路：雙指針

先審題，首先題目中所給的數(shù)組是有序的，因?yàn)檫@個(gè)前提，我們可以考慮使用雙指針的思路，縮小范圍，進(jìn)而求得答案。

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

• 返回的下標(biāo)值，并不是從零開始，而是從 1 開始
• 題目有唯一解，所以求得答案可直接返回。

現(xiàn)在說下算法的具體思路：

• 定義雙指針 left, right，分別指向有序數(shù)組的首尾；
• 令兩個(gè)指針?biāo)鶎?yīng)的數(shù)字相加，設(shè)為 two_sum，與 target 進(jìn)行比較：
  • 若 two_sum == target，返回 [left + 1, right + 1]（因?yàn)榉祷叵聵?biāo)值從 1 開始）
  • 若 two_sum > target，則向前移動(dòng)右指針；
  • 若 two_sum < target，則向后移動(dòng)左指針。

算法實(shí)現(xiàn)的過程如下圖：

圖解

具體的代碼實(shí)現(xiàn)如下。

代碼實(shí)現(xiàn)

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

        while left < right:
            # 令指針?biāo)鶎?yīng)的數(shù)字相加，與 target 作比較
            two_sum = numbers[left] + numbers[right]
            # 相等時(shí)，返回索引值，因?yàn)橄聵?biāo)從 1 開始計(jì)算，要相應(yīng) +1
            if two_sum == target:
                return [left + 1, right + 1]
            # 兩數(shù)之和大于 target，移動(dòng)右指針縮小兩數(shù)和
            elif two_sum > target:
                right -= 1
            # 兩數(shù)和小于 target，移動(dòng)左指針增大兩數(shù)和
            else:
                left += 1

        return None

實(shí)現(xiàn)結(jié)果

實(shí)現(xiàn)結(jié)果

歡迎關(guān)注

公眾號(hào) 【書所集錄】