和为S的两个数字——题解

方法一：之前见过改题目的精简版，不用判断乘积最小，只用判断数字序列中是否包含有两个数字和为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;
    }
}