[python2] 57 和为S的两个数

题目描述

题目思路及代码如下：

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        # 使用左右两个指针来遍历整个数组。左指针从数组头部开始，右指针从数组尾部开始，若两数和等于tsum，则返回两个数；
        # 若两数和大于tsum，则右指针向左移一位；若两数和小于tsum,则左指针右移一位
        sumS = []
        leftPtr = 0
        rightPtr = len(array) - 1
        while leftPtr <= rightPtr: 
            if array[leftPtr] + array[rightPtr] == tsum:
                sumTemp = []
                sumTemp.append(array[leftPtr])
                sumTemp.append(array[rightPtr])
                sumS.append(sumTemp)
                # 这里要注意，由于不是只输出一组和为S的数字就可以了，而是需要进一步比较乘积，因此这里还需要继续遍历，直到遍历完所有的组合
                leftPtr += 1
            elif array[leftPtr] + array[rightPtr] > tsum:
                rightPtr -= 1
            else:
                leftPtr += 1
        # sumS中保存了所有和为tsum的两个数，以[[],[],[]...]的形式保存
        # 下面需要判断计算每两个数的乘积，返回乘积最小的两个数
        if len(sumS) == 0:
            return []
        elif len(sumS) > 1:
            multiply = []
            for sumSS in sumS:
                multiplyTemp = sumSS[0] * sumSS[1]
                multiply.append(multiplyTemp)
            sumMin = multiply[0]
            indexMin = 0
            for index in range(1, len(multiply) - 1):
                if multiply[index] < sumMin:
                    sumMin = multiply[index]
                    indexMin = index
            return sumS[indexMin]
        elif len(sumS) == 1:
            return sumS[0] #对于输出部分需要注意，虽然说要输出两个数，但是这两个数作为一个list整体输出也是可以的

if __name__ == "__main__":
    s = Solution()
    array = [1, 2, 4, 7, 11, 15]
    tsum = 15
    a, b = s.FindNumbersWithSum(array, tsum)
    print(a, b)