42.和为S的两个数字

题目描述

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

解题思路

题目中给出是一个递增排序的数组。我们设置两个指针分别指向数组的第一个数字和最后一个数字，求和与S比大小，相等则输出两个数字，此时的两个数字的乘积肯定是最小的；小于则前面的指针后移；大于则后面的指针前移。

Python代码如下

# -*- coding:utf-8 -*- class Solution: def FindNumbersWithSum(self, array, tsum): # write code here if len(array) <= 1: return [] low, high = 0, len(array) - 1 while low < high: if array[low] + array[high] == tsum: return array[low],array[high] elif array[low] + array[high] < tsum: low += 1 else: high -= 1 return []