题目描述

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