題目描述

輸入一個遞增排序的數(shù)組和一個數(shù)字S，在數(shù)組中查找兩個數(shù)，使得他們的和正好是S，如果有多對數(shù)字的和等于S，輸出兩個數(shù)的乘積最小的。
輸出描述:
對應(yīng)每個測試案例，輸出兩個數(shù)，小的先輸出。

解題思路一：參考two sum問題，該方法時間復(fù)雜度為O(n),空間復(fù)雜度為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.注意該數(shù)組為一個遞增有序的數(shù)組
1.設(shè)定兩個指針p和q,開始時分別指向array[0]和array[-1]
2.當(dāng)p和q兩個指針對應(yīng)位置的值之和s大于tsum時，q-=1
3.當(dāng)p和q兩個指針對應(yīng)位置的值之和s小于tsum時，p+=1
4.通過該方法首次找到的一對就是乘積最小的那一對。

證明如下：

假設(shè)找到的是[x,y]。那么有,,
于是有：
于是有：
于是有：
我們發(fā)現(xiàn)是一個遍歷為的二次函數(shù)，對稱軸為Y軸，頂點為，開口向下，在的情況下，隨著d的增加而減小。而首次找到的那一對最大。

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        #0.注意該數(shù)組為一個遞增有序的數(shù)組
        #1.設(shè)定兩個指針p和q,開始時分別指向array[0]和array[-1]
        #2.當(dāng)p和q兩個指針對應(yīng)位置的值之和s大于tsum時，q-=1
        #3.當(dāng)p和q兩個指針對應(yīng)位置的值之和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 []