很久没有刷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))