和为S的两个数字
程序员文章站
2024-03-15 21:30:30
...
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 []
上一篇: 二分查找-006-旋转数组的最小数字
下一篇: 和为s的两个数字 java