1 題目

給你一個(gè)下標(biāo)從 1 開始的整數(shù)數(shù)組 numbers ，該數(shù)組已按 非遞減順序排列 ，請你從數(shù)組中找出滿足相加之和等于目標(biāo)數(shù) target 的兩個(gè)數(shù)。如果設(shè)這兩個(gè)數(shù)分別是 numbers[index1] 和 numbers[index2] ，則 1 <= index1 < index2 <= numbers.length 。

以長度為 2 的整數(shù)數(shù)組 [index1, index2] 的形式返回這兩個(gè)整數(shù)的下標(biāo) index1 和 index2。

你可以假設(shè)每個(gè)輸入 只對應(yīng)唯一的答案 ，而且你 不可以 重復(fù)使用相同的元素。

你所設(shè)計(jì)的解決方案必須只使用常量級的額外空間。

示例 1：

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

示例 2：

輸入：numbers = [2,3,4], target = 6
輸出：[1,3]
解釋：2 與 4 之和等于目標(biāo)數(shù) 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

輸入：numbers = [-1,0], target = -1
輸出：[1,2]
解釋：-1 與 0 之和等于目標(biāo)數(shù) -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示：

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers 按 非遞減順序 排列
• -1000 <= target <= 1000
• 僅存在一個(gè)有效答案

2 解答

1 對向雙指針

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        index_left = 0
        index_right = len(numbers) - 1

        while index_left<index_right:
            sum = numbers[index_right] + numbers[index_left]
            if sum == target:
                break
            if sum>target:
                index_right -=1

            if sum<target:
                index_left+=1

        return [index_left+1 , index_right+1]

2 哈希表

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        map = {}
        for index , value in enumerate(numbers):
            map[value] = index

        for j in range(0 , len(numbers) , 1):
            if (target - numbers[j] in map) and (j != map[target - numbers[j]]):
                return [j+1 , map[target - numbers[j]]+1]