题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。
解题思路一：参考two sum问题，该方法时间复杂度为O(n),空间复杂度为O(n)，代码有写冗长。思路二代码较为简单。
# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
adict = {}
res_truple = []
for i in range(len(array)):
target = tsum - array[i]
if adict.get(target) is not None:
res_truple.append([target,array[i]])
else:
adict[array[i]] = 1
if len(res_truple)==0:
return []
product = res_truple[0][0]*res_truple[0][1]
small = min(res_truple[0][0],res_truple[0][1])
big = max(res_truple[0][0],res_truple[0][1])
for i in range(1,len(res_truple)):
if product>res_truple[i][0]*res_truple[i][1]:
product = res_truple[i][0]*res_truple[i][1]
small = min(res_truple[i][0], res_truple[i][1])
big = max(res_truple[i][0], res_truple[i][1])
return [small,big]
解题思路二：
0.注意该数组为一个递增有序的数组
1.设定两个指针p和q,开始时分别指向array[0]和array[-1]
2.当p和q两个指针对应位置的值之和s大于tsum时，q-=1
3.当p和q两个指针对应位置的值之和s小于tsum时，p+=1
4.通过该方法首次找到的一对就是乘积最小的那一对。
证明如下：
假设找到的是[x,y]。那么有,
,
于是有：
于是有：
于是有：
我们发现是一个遍历为
的二次函数，对称轴为Y轴，顶点为
，开口向下，在
的情况下，随着d的增加而减小。而首次找到的那一对
最大。
# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
#0.注意该数组为一个递增有序的数组
#1.设定两个指针p和q,开始时分别指向array[0]和array[-1]
#2.当p和q两个指针对应位置的值之和s大于tsum时，q-=1
#3.当p和q两个指针对应位置的值之和s小于tsum时，p+=1
p = 0
q = len(array)-1
while p<q:
s = array[p] + array[q]
if s>tsum:
q -= 1
elif s<tsum:
p += 1
elif s == tsum:
return [array[p],array[q]]
return []
