剑指offer42

剑指offer42：和为S的两个数字

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，
使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输出描述:
对应每个测试案例，输出两个数，小的先输出。

解法一：基于暴力法

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array, int sum) {
        int flag = INT_MAX;
        vector<int> b(2, -1);
        for (int i = 0; i<array.size(); i++)
            for (int j = i + 1; j<array.size(); j++)
            {
                if (array[i] + array[j] == sum)
                {
                    if (array[i] * array[j]<flag)
                    {
                        b[0] = array[i];
                        b[1] = array[j];
                        flag = b[0] * b[1];
                    }

                }
            }
        if (b[0] + b[1] != -2)
            return b;
        else
            return {};

    }
};

解法二：基于map的方法

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array, int sum) {
        map<int, int> mp;
        vector<int> b(2, -1);
        int flag = INT_MAX;
        for (int i = 0; i<array.size(); i++)
        {
            mp[array[i]] = i;
            if (mp.count(sum - array[i]) && mp[sum - array[i]] != i)
            {
                if (flag>(array[i] * (sum - array[i])))
                {
                    b[1] = array[i];
                    b[0] = sum - array[i];
                    flag = b[0] * b[1];
                }
            }
        }
        if (flag<INT_MAX)
            return b;
        else
            return {};
    }
};