题目描述
输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
输出描述:
对应每个测试案例,输出两个数,小的先输出。
解题思路
使用两个指针,分别指向数组的头和尾,判断他们之和是否等于S,等于直接返回,小于S则将第一个指针向后移动一位,大于S将后一个指针向前移动一位。
注:对于索对数字满足条件的,乘积最小的即为找到的第一对(不用刻意判断)。
代码
Python(2.7.3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
small, big = 0, len(array) - 1
mid = len(array) // 2 + 1
while small < big and small < mid:
tmp = array[small] + array[big]
if tmp < tsum:
small += 1
elif tmp > tsum:
big -= 1
else:
return [array[small], array[big]]
return []运行时间:26ms
占用内存:5720k