[BinarySearch]167 Two Sum II - I

• 分类：BinarySearch

• 考察知识点：BinarySearch\Two Pointer\HashMap

• 最优解时间复杂度：O(logn~n)BinarySearch,O(n)TwoPointer\HashMap

• 最优解空间复杂度：O(1)BinarySearch\TwoPointer O(n)HashMap

167. 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.

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.

代码：

Two Pointer方法:

class Solution:
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        #判断边界条件
        if len(numbers)<=1:
            return [-1,-1]
        
        start=0
        end=len(numbers)-1
        while (end-start>1):
            if numbers[start]+numbers[end]==target:
                return [start+1,end+1]
            elif numbers[start]+numbers[end]<target:
                start+=1
            else:
                end-=1
        
        return [start+1,end+1]

HashMap方法:

class Solution:
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(numbers)<=1:
            return[-1,-1]
        
        num_dict={}
        for i,n in enumerate(numbers):
            if target-n in num_dict:
                return [num_dict[target-n],i+1]
            num_dict[n]=i+1
        
        return [-1,-1]

BinarySearch方法:

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

---

讨论：

1.这道题是001的升级版,然后有三种做法，Two Pointer, Binary Search和HashMap，事实证明HashMap效果最快
2.这道题是sorted，感觉就是要用到sorted的特性，显然Two Pointer和Binary Search都用到了这个特性，而且Two Pointer效果更好？

HashMap还是最快