Two sum(input array is sorted)

题目描述

array已经sorted

解题方法

已经sorted就不用担心改变顺序，直接使用two pointer方法做

Solution

Two pointer

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        length = len(numbers)
        if length < 2:
            return []
        #sort to allow two-pointer algorithm and skip duplicate
        numbers.sort()
        start, end = 0, length - 1
        while start < end:
            #skip duplicate elements
            if start != 0 and numbers[start] == numbers[start-1]:
                start += 1
            elif end != length - 1 and numbers[end] == numbers[end + 1]:
                end -= 1
            else:
                curSum = numbers[start] + numbers[end]
                if curSum == target:
                    return [start + 1, end + 1]
                elif curSum < target:
                    start += 1
                else:
                    end -= 1
        return []

can do a binary search

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        length = len(numbers)
        if length < 2:
            return [0, 0]

        index1 = 0
        index2 = 0
        for i, num in enumerate(numbers):
            foundPair, index = self.search(i + 1, length - 1, numbers, target - num)
            if foundPair:
                index1 = i + 1
                index2 = index + 1
                return [index1, index2]

        return [index1, index2] 

    def search(self, start, end, numbers, t):
        while start + 1 < end:
            mid = start + (end - start) / 2
            if numbers[mid] == t:
                return True, mid
            elif numbers[mid] < t:
                start = mid
            else:
                end = mid
        if numbers[start] == t:
            return True, start
        if numbers[end] == t:
            return True, end

        return False, 0