两数之和 II

很久没有刷leetcode，习惯不能丢。

打算继续保持，从海外转到“力扣”，继续完成。

一、题目描述

二、解答

　　根据题意，有序数组，并且都是有解的。

　　如果单纯一个一个比对，也能找到想要的结果，只不过算法复杂度最高。

　　先确定左值，现在的题目就变成在有序数组中寻找一个数了；

　　　　常规有二分查找，哈希；二分查找适合有序的数组，哈希适合无序，需要先建立哈希表。

　　　　本题适合二分查找

　　代码：

 1 class Solution:
 2     def twoSum(self, numbers, target):
 3         for i in range(int(len(numbers)/2)):
 4             find = self.binarySearch(numbers, i+1, len(numbers)-1, target-numbers[i])
 5             if find > 0:
 6                 return [i+1, find+1]
 7 
 8     def binarySearch(self, numbers, startIndex, endIndex, target):
 9         if (target < numbers[startIndex]) or (target > numbers[endIndex]) or (startIndex > endIndex):           
10            return -1
11         mid = int((startIndex + endIndex) / 2)
12         if numbers[mid] > target:
13             return self.binarySearch(numbers, startIndex, mid-1, target)
14         elif numbers[mid] < target:
15             return self.binarySearch(numbers, mid+1, endIndex, target)
16         return mid
17 
18 
19 if __name__ == "__main__":
20     s = Solution()
21     print(s.twoSum([2, 7, 11, 15], 9))