剑指offer-和为S的两个数字

本文为剑指 offer 系列第四十一篇。
主要知识点为数组的遍历，找个map存一下元素及其出现次数即可，比较简单。

题目描述

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

解题思路

思路1

可以通过两层循环来解决。但是时间复杂度是O(n^2)。或者这里是有序的，可以在内层循环用二分查找，那么时间复杂度将会变为O(nlgn)。

思路2

使用map来保存所有元素的出现次数，然后重新遍历一遍数组，查找是否存在和当前数值的和为S的数字。如果两个值相同，需要出现至少两次，不能把同一个元素用两遍。
如果有多对数字满足条件，就要选择乘积最小的。两个数的和一定时，值越接近，乘积越大，所以我们从数组的最小值开始找，找到第一对就可以返回。

这里扩展一下，之前在leetcode上还有一道类似的题目，要求返回两个值的索引，所以map的value要保存索引。本题只要求返回两个值，用出现次数就够了。

解题代码

思路2代码

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        unordered_map<int,int> mmap;
        for(auto a:array){
            mmap[a]++;
        }
        for(auto a:array){
            long long other = (long long)sum-a;
            if(other < INT_MIN || other > INT_MAX) continue;
            auto it = mmap.find((int)other);
            if(it != mmap.end() && (other != a || it->second > 1)){
                return {a,(int)other};
            }
        }
        return {};
    }
};

时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！