167. Two Sum II - Input array is sorted

# Easy

Two methods:

1. fixed pointer i, binarySearch in interval [i+1, len(nums)-1] to fined new target = target - numbers[i].

2. two dynamic pointers i and j, if num[i]+num[j]>target, j --; if num[i]+num[j]<target, i ++. This method is more efficient.

Python(1)

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            new_target = target-numbers[i]
            start = i+1
            end = len(numbers)-1
            while start <= end:
                mid = start + (end-start)//2
                if new_target > numbers[mid]:
                    start = mid+1
                elif new_target < numbers[mid]:
                    end = mid-1
                else:
                    return [i+1, mid+1]

Time complexity = $O(NlgN)$

Python(2)

Time complexity = $O(n)$

class Solution:      
    def twoSum(self, numbers, target):
        i = 0
        j = len(numbers)-1
        while True:
            if numbers[i] + numbers[j] > target:
                j = j - 1
            elif numbers[i] + numbers[j] < target:
                i = i + 1
            else:
                return [i+1, j+1]