问题描述

给你一个下标从1开始的整数数组numbers,该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

示例1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

解题思路：

双指针

由于需要寻找数组中两个元素相加之和等于target的元素下标。且数组是非递减排列的，因此可以考虑使用双指针的方式。

解法1

left指针以数组的第一个位置作为初始条件，right指针始终以left指针+1位置作为初始条件。先用left指针确定第一个元素，然后使用right指针寻找数组中是否有和left指针对应元素相加等于target值的，如果当right指针和left指针的和大于target时，则证明数组中没有与left指针对应元素相加等于target的数，因此，将left指针右移。依此循环，上述过程如图所示：

def twoSum(numbers, target):
    left = 0
    length = len(numbers)
    while left <= length - 2:
        right = left + 1
        while right < length:
            if numbers[left] + numbers[right] == target:
                return [left + 1, right + 1]
            elif numbers[left] + numbers[right] > target:
                break
            else:
                pre_right = numbers[right]
                while numbers[right] == pre_right and right < length - 1:
                    right += 1
                if right == length - 1:
                    break
        if numbers[right] + numbers[left] == target:
            return [left + 1, right + 1]
        pre_left = numbers[left]
        while numbers[left] == pre_left:
            left += 1

解法2

left指针以数组的第一个位置作为初始条件，right指针以数组最后一个位置作为初始条件，left指针代表的是最小的元素值，right指针代表的是最大的元素值。若left指针对应的元素值和right指针对应的元素值相加小于target，则证明数组中没有与left指针对应元素相加等于target值得元素，left指针向右移。反之，若和大于target，则证明数组中没有与right值相加等于target值的元素，right右移。依此循环，上述过程如图所示：

def twoSum2(numbers, target):
    left = 0
    right = len(numbers) - 1
    while left <= right:
        if numbers[left] + numbers[right] == target:
            return [left + 1, right + 1]
        elif numbers[left] + numbers[right] < target:
            left += 1
        else:
            right -= 1

可以看出，第二种方法比第一种方法的效率要高很多

直接遍历

依次遍历数组中的每个元素，判断target-元素i的值在数组中是否存在，若存在，则放回

def twoSum(numbers, target):
    for i in range(len(numbers)):
        if target-numbers[i] in numbers:
            if numbers.index(target-numbers[i]) == i:
                return [i+1,i+2]
            return [i+1,numbers.index(target-numbers[i])+1]
            break