欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

和为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 []

 

相关标签: 和为S的两个数字