描述

这是一篇针对初学者的题解。共用两种方法解决。
知识点：数组，哈希，双指针
难度：一星

题解

题目抽象：给定一个数组，返回两个数字和为sun且乘积最小的两个数字。

方法一：哈希法

要求a + b = sum, 如果已知a， 那么b = sum - a
所以可以先将b添加入哈希中，然后遍历一遍数组设为a， 在哈希中寻找是否存在sum-a，然后再更新乘积最小值

代码

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        if (array.empty()) return vector<int>();
        int tmp = INT_MAX;
        pair<int, int> ret;
        unordered_map<int,int> mp;
        for (int i=0; i<array.size(); ++i) {
            mp[array[i]] = i;
        }
        for (int i=0; i<array.size(); ++i) {
            if (mp.find(sum-array[i]) != mp.end()) {
                int j = mp[sum-array[i]];
                if ( j > i && array[i]*array[j] < tmp) {
                    tmp = array[i] * array[j];
                    ret = {i, j};
                }
            }
        }
        if (ret.first == ret.second) return vector<int>();
        return vector<int>({array[ret.first], array[ret.second]});

    }
};

时间复杂度：O(n)
空间复杂度：O(n)

方法二：双指针

因为数组是有序的，所以可以用双指针，指向数组的首尾，具体步骤如下：
1.初始化：指针i指向数组首， 指针j指向数组尾部
2. 如果arr[i] + arr[j] == sum , 说明是可能解
3. 否则如果arr[i] + arr[j] > sum, 说明和太大，所以--j
4. 否则如果arr[i] + arr[j] < sum, 说明和太小，所以++i

代码

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        if (array.empty()) return vector<int>();
        int tmp = INT_MAX;
        pair<int, int> ret;
        int i = 0, j = array.size();
        while (i < j) {
            if (array[i] + array[j-1] == sum) {
                if (array[i]*array[j-1] < tmp) {
                    tmp = array[i] * array[j-1];
                    ret = {i, j-1};
                }
                ++i, --j;
            }
            else if (array[i] + array[j-1] < sum) {
                ++i;
            }
            else {
                --j;
            }
        }
        if (ret.first == ret.second) return vector<int>();
        return vector<int>({array[ret.first], array[ret.second]});
    }
};

时间复杂度：O(n)
空间复杂度：O(1)