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

本文为剑指 offer 系列第四十一篇。
主要知识点为数组的遍历，找个set存一下想要的元素有没有存在即可，比较简单。

题目描述

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

解题思路

思路1

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

思路2

使用set来保存所有元素，然后重新遍历一遍数组，查找是否存在和当前数值的和为S的数字。
如果有多对数字的和等于S，输出两个数的乘积最小的，这个有一个类似于贪心的操作就是如果和一定，那么两个值越接近，那么乘积越大，对应的，我们要求找乘积最小的，所以只要从最小值开始遍历即可。
这里扩展一下，之前在leetcode上还有一道题目同样是找两个和为S的数字，但是那个题目要求返回的是两个值的索引，那个地方要用map,对应的key和value分别是值和索引。而本题目中只要求返回两个值即可，所以只要用set来确认有没有对应元素存在即可。

解题代码

思路2代码

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        unordered_set<int> mset;
        for(auto a:array){
            mset.insert(a);
        }
        for(auto a:array){
            if(mset.count(sum-a)){
                return {a,sum-a};
            }
        }
        return {};
    }
};

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