方法一:之前见过改题目的精简版,不用判断乘积最小,只用判断数字序列中是否包含有两个数字和为S。最直观的想法的是使用一个双重循环,但是这样效率未免太低。考虑到a+b=sum,则b=sum-a。可以使用一个HashMap存储。因此我们可以先将b保存在HashMap中,然后再遍历计算sum-a,如果找到一个sum-a的值在HashMap中,则说明存在两数之和为sum。然后在遍历的同时记录满足条件的数字的乘积。
# -*- coding:utf-8 -*- class Solution: def FindNumbersWithSum(self, array, tsum): # write code here mydict = {} res = [] product = pow(2, 31)-1 for i,v in enumerate(array): if tsum-array[i] in mydict: # 找到了一个和为S的 j = mydict[tsum-array[i]] tmpproduct = v*(tsum-array[i]) if tmpproduct < product: if i < j: res = [array[i], array[j]] else: res = [array[j], array[i]] else: mydict[v] = i return res
方法二:考虑到给定的数组是一个递增的数组,因此可以使用双指针进行解答,每一次计算两个指针对应的数字的和,根据和与S的大小关系调整指针的指向。直到第一次找到两个数字之和等于S,则输出。为什么是第一个找到的呢,因为给定的数组是一个递增数组。举个例子,array=[1,2,3,4,5,6,7,8,9],S是10,很明显第一个找到满足和为S的两个数的乘积就是最小的。
import java.util.*; public class Solution { public ArrayList FindNumbersWithSum(int [] array,int sum) { ArrayList res = new ArrayList(); if(array.length<=1) return res; // 使用快慢指针,因为是排序的数组,所以最先找到的肯定乘积最小,最外层的最小 //比如【0,1,2,3,4,5,6,7,8,9,10】 int begin = 0; int end = array.length - 1; while (begin < end){ int currentSum = array[begin] + array[end]; if (currentSum > sum) end--; else if(currentSum < sum) begin++; else if (currentSum==sum){ res.add(array[begin]); res.add(array[end]); break; // 找到之后 第一个直接break } } return res; } }
反思:做题目的时候最好可以先写边界条件,不然容易忽略一些特殊情况。