Two Sum II - Input array is sorted

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. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would haveexactlyone solution and you may not use thesameelement twice.

Input:numbers={2, 7, 11, 15}, target=9 Output:index1=1, index2=2

注意题目说了两个重要条件：1，有序数组；2，有唯一解。所以解的两个数一定都是数组中唯一存在的数

注意：返回的index要加一，题目要求index从1开始。

1. Hashmap

时间复杂度O(n)，空间复杂度O(n)。

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashmap = {}
        for i in xrange(len(numbers)):
            hashmap[numbers[i]] = i
        for i in xrange(len(numbers)):
            new =target - numbers[i]
            if new in hashmap:
                return i+1, hashmap[new]+1

2. Two pointer

初始化的时候第一个指针left在下标为0的位置，第二个指针right在下标为n - 1的位置。通过比较计算的和与target，移动指针，缩小查找范围。

比如，一开始的时候，left = 0, right = n - 1，计算此时的和 sum = nums[left] + nums[right]。

如果此时的和 > target，说明右边太大了，right – 。 如果 和 < target, 说明左边太小了，left ++。 如果刚好等于，返回此时的left, right。

时间复杂度为O(n), 空间复杂度为O(1)。

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        left = 0
        right = len(numbers)-1
        while left < right:
            if numbers[left] + numbers[right] == target:
                return left+1,right+1
                break
            elif numbers[left] + numbers[right] < target:
                left += 1
            else:
                right -= 1

3. Binary search

因为考虑到这是一个有序的数组，所以很自然地想往二分搜索上靠。

先固定第一个数，假设为nums[0], 那么在下表为1 .. n - 1上进行二分搜索，查找有没有值为target - nums[0]。

固定第一个数为nums[1], 在 2 .. n - 1上二分查找。

时间复杂度为O(nlogn), 空间复杂度为O(1)。

二刷：

Two pointer 没记住！

Binary Search

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in xrange(len(numbers)):
            start,end = i+1,len(numbers)-1
            value = target - numbers[i]
            while start+1 < end:
                mid = (start+end)/2
                if numbers[mid] < value:
                    start = mid
                else:
                    end = mid
            if numbers[start] == value:
                return i+1, start+1
            elif numbers[end] == value:
                return i+1, end+1
            else:
                continue