题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输出描述:

对应每个测试案例，输出两个数，小的先输出。

# -*- coding: utf-8 -*-
# @Time         : 2019-10-15 22:26
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : FindNumbersWithSum.py
# @Blog         : https://sysujayce.github.io/
# @Github       : https://github.com/SysuJayce


class Solution:
    """
    题目已经说明了这个数组是有序的，且是升序排序的，那么我们就需要利用到这个有利的条件。

    既然已经是升序，那么我们可以维护两个指针，分别指向数组的头尾，然后用O(n)时间扫一遍数组即可。
    具体来说，
    如果 array[left] + array[right] > target，那么说明当前的和大了，我们需要将右指针往左
    如果 array[left] + array[right] < target，那么说明当前的和小了，我们需要将左指针往右
    如果 array[left] + array[right] == target，那么这时候需要比较乘积是否比之前的要小，然后左右指针往中间靠
    """
    def FindNumbersWithSum(self, array, tsum):
        if not array:
            return []
        ans = ()
        min_product = float('inf')
        left, right = 0, len(array) - 1
        while left < right:
            if array[left] + array[right] == tsum:
                product = array[left] * array[right]
                if product < min_product:
                    min_product = product
                    ans = (array[left], array[right])
                left += 1
                right -= 1
            elif array[left] + array[right] > tsum:
                right -= 1
            else:
                left += 1
        return ans