两数之和 II - 输入有序数组

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

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

 

一、题目描述

两数之和 II - 输入有序数组

二、解答

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

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

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

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

    本题适合二分查找

  代码:

  

 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))

 

上一篇:sendmail 出现 My unqualified host name的解决办法


下一篇:php.ini,sendmail配置以使用php脚本发送电子邮件