[leetcode] 167 - sum of two numbers II - enter an ordered array

I'll give you a subscript from 1 The starting array of integers numbers , The array has been pressed Non decreasing order , Please find out from the array that the sum satisfying the addition is equal to the target number target Two numbers of . Let these two numbers be numbers[index1] and numbers[index2] , be 1 <= index1 < index2 <= numbers.length .

In length 2 Array of integers for [index1, index2] Returns the subscript of these two integers in the form of index1 and index2.

You can assume that each input Only corresponding to the only answer , And you Can not be Reuse the same elements .

The solution you design must use only constant level extra space .

Example 1：

Input ： numbers = [2,7,11,15], target = 9
Output ： [1,2]
explain ： 2 And 7 The sum is equal to the number of targets 9 . therefore index1 = 1, index2 = 2 . return [1, 2] .

Example 2：

Input ： numbers = [2,3,4], target = 6
Output ： [1,3]
explain ： 2 And 4 The sum is equal to the number of targets 6 . therefore index1 = 1, index2 = 3 . return [1, 3] .

Example 3：

Input ： numbers = [-1,0], target = -1
Output ： [1,2]
explain ： -1 And 0 The sum is equal to the number of targets -1 . therefore index1 = 1, index2 = 2 . return [1, 2] .

Tips ：

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers Press Non decreasing order array
• -1000 <= target <= 1000
• There is only one valid answer

# The first is to use double circulation , Sure enough, it timed out 
class Solution(object):
    def twoSum(self, numbers, target):
        length = len(numbers)
        first = 0
        second = 1
        while first<length-1:
            while second<length:
                if numbers[first]+numbers[second]==target:
                    return [first+1,second+1]
                second+=1
            first+=1
            second=first+1
# Then replace the second level loop with binary search ：
class Solution(object):
    def twoSum(self, numbers, target):
        length = len(numbers)
        first = 0
        while first<length-1:
            left = first+1
            right = length-1
            while left<=right:
                mid = int((left+right)/2)
                if numbers[first]+numbers[mid]==target:
                    return [first+1,mid+1]
                elif numbers[first]+numbers[mid]<target:
                    left = mid+1
                else:
                    right = mid-1
            first+=1
        return [-1,-1]

# Double pointer 
class Solution(object):
    def twoSum(self, numbers, target):
        length = len(numbers)
        left = 0
        right = length-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
        return [-1,-1]