[剑指Offer]和为S的两个数字

题目描述

输入一个递增排序的数组和一个数字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