剑指42-和为S的两个数字

Posted on | In |

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输出描述:

对应每个测试案例，输出两个数，小的先输出。

  • 乘积最小，肯定是两头优先，即较小值从序列最左侧开始找。
  • 较小值上界是0.5*tsum。
1
2
3
4
5
6
7
8
9
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        if len(array) < 2:
            return []
        for num in array:
            if num >= 0.5*tsum:
                return []
            if tsum - num in array:
                return [num, tsum-num]
  • 将查看数组是否包含某元素的操作，即'if tsum-num in array'，替换成了二分查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        def search(num, array):
            if len(array) == 0:
                return False
            s, t = 0, len(array)-1
            while s < t:
                mid = (s+t)>>1
                if array[mid] == num:
                    return True
                elif array[mid] > num:
                    t = mid
                else:
                    s = mid + 1
            return array[s] == num
          
        if len(array) < 2:
            return []
        for ix, num in enumerate(array):
            if num >= 0.5*tsum:
                return []
            if search(tsum - num, array[ix+1:]):
                return [num, tsum-num]