經(jīng)典的twosum問(wèn)題變種，傳入已排序的序列

題目如下

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:
Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

第一種解法，利用二分查找

時(shí)間復(fù)雜度O(n*log(n)) 空間復(fù)雜度O(1)
解題思路：
由于傳入的是已排序序列，所以我們可以利用二分查找的高性能來(lái)幫助我們優(yōu)化查找另一個(gè)數(shù)的過(guò)程。
插入一個(gè)二分查找的介紹
二分查找：
Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.complexity is log(len(data))
代碼實(shí)現(xiàn)如下

def twoSumSorted(numbers,target):
    for n in range(0,len(numbers)):
        other = target-numbers[n]
        #As we won't use same element twice, so we could screen the rest of the array without the current elements
        low,high = n+1,len(numbers)-1
        while low <= high:
            middle = (low+high)//2
            if other == numbers[middle]:
                return [n+1,middle+1]
            elif other > numbers[middle]:
                low = middle+1
            else:
                high = middle-1

第二種解法，兩個(gè)指針

時(shí)間復(fù)雜度O(n),空間復(fù)雜度O(1)
解題思路：
假設(shè)我們創(chuàng)建了兩個(gè)索引 數(shù)組中的第I個(gè)和第J個(gè)元素（I<J），那么我們可以得到如下三種情況：

1. I+J > target,由于數(shù)組是已排序數(shù)組，那么J元素的值是大于I元素的值，此時(shí)我們?cè)賹?duì)I進(jìn)行自加只會(huì)讓兩者的和更大，所以此處我們對(duì)J進(jìn)行自減
2. I+J < target,同理，我們只能對(duì)I進(jìn)行自加操作
3. I+J = target, 完結(jié)撒花
   代碼實(shí)現(xiàn)如下

def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        # two pointer solution
        i,j = 0,len(numbers)-1
        # assume the array is already sorted and we cannot use the same element twice
        while i < j:
            sum = numbers[i]+numbers[j]
            # as j is the largest number in the array, if sum > target, we should decrement j 
            if sum > target:
                j -= 1
            # i is the smallest number in the array, if sum < target, we should increment i
            elif sum < target:
                i += 1
            else:
                return [i+1,j+1]