leetcode 两数之和II-输入有序数组

167. 两数之和 II - 输入有序数组

给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

示例 1：

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

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]

提示：

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers 按 非递减顺序 排列
• -1000 <= target <= 1000
• 仅存在一个有效答案

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """

思考

写两个for循环，然后将每个列表的两个值一一相加，直到得出目标值。

通过enumerate()得出下标

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        num = len(numbers)
        for i in range(0,num):
            for k in range(i+1,num):
                if numbers[i]+numbers[k] == target:
					return i+1,k+1

但这样并没有通过，超出了时间限制，还记得二分查找吗？

非递归二分查找

def binary_search(list,item):
    # 列表的头和尾，代表着数组范围的最小和最大
    low = 0
    high = len(list) - 1

    # 当找到item的时候，low是小于high，也有可能相等
    while low <= high:
        mid = (low + high)//2
        # 取数组的中间值
        guess = list[mid]
        # 如果中间值等于索引值，那么就返回中间值的下标
        if guess == item:
            return mid

        # 如果中间值>索引值，因为不包含中间值，所以最大范围high=中间值的下标往左移1位
        if guess > item:
            high = mid - 1

        # 如果中间值<索引值，因为不包含中间值，所以最小范围low=中间值的下标往右移1位
        else:
            low = mid + 1
    return None
    
my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list,3))

# 改进后             
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        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 = left + 1
            else:
                right = right - 1

附递归二分查找

def binary_search(list,data):
    n = len(list)
    mid = n // 2
    if list[mid] > data:
        return binary_search(list[0:mid],data)
    elif list[mid] < data:
        return binary_search(list[mid+1:],data)
    else:
        return mid

java双指针

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0, j = numbers.length - 1; i < j;) {
            int sum = numbers[i] + numbers[j];
            if (sum == target) return new int[] {i + 1, j + 1};
            else if (sum > target) j--;
            else i++;
        }
        return null;
    }
}

---