刷题笔记06-20

经典的twosum问题变种，传入已排序的序列

题目如下

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.

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

时间复杂度O(n*log(n)) 空间复杂度O(1)
解题思路：
由于传入的是已排序序列，所以我们可以利用二分查找的高性能来帮助我们优化查找另一个数的过程。
插入一个二分查找的介绍
二分查找：
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))
代码实现如下

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

第二种解法，两个指针

时间复杂度O(n),空间复杂度O(1)
解题思路：
假设我们创建了两个索引 数组中的第I个和第J个元素（I<J），那么我们可以得到如下三种情况：

1. I+J > target,由于数组是已排序数组，那么J元素的值是大于I元素的值，此时我们再对I进行自加只会让两者的和更大，所以此处我们对J进行自减
2. I+J < target,同理，我们只能对I进行自加操作
3. I+J = target, 完结撒花
   代码实现如下

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]