Two sum II 二值和2

Easy, Array/String

给定升序排列的整数列，寻找两数加起来等于目标值。你的函数应当返回两数的位置（1-based)。假设只有一个解且不要两次使用同一个数。

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

Solution:

此题依然可以使用二值和1的解法利用字典来解，复杂度可以控制在O(n)。

不过这里数列加了一个限制条件：升序排列。所以我们可以进一步提高算法效率，使用两个指针同时指向序列头和尾，然后向中间移动，移动过程检查指针指向的数是否加起来为目标值。主需要消耗O(1) space。

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