【剑指offer】题解：和为S的两个数字

题目描述

输入一个数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。
如果有多对数字的和等于 s，输出任意一对即可。
你可以认为每组输入中都至少含有一组满足条件的输出。

数据范围
数组长度 [1,1002]

样例

样例
输入：[1,2,3,4] , sum=7输出：[3,4]

---

1.（暴力）O(n^2)

双层for循环遍历即可。注意控制边界情况
时间复杂度 O(n)

//c++代码
class Solution {
public:vector<int> findNumbersWithSum(vector<int>& nums, int target) {for(int i=0;i<nums.size();i++){for(int j=i+1;j<nums.size();j++){if(nums[i] + nums[j] == target){return {nums[i],nums[j]};}}}return {-1,-1};}
};

2.(哈希) O(n)

        由于我们只需要找到 a + b == target 的一对，所以我们先遍历,如果当前的数 a 和 target 满足哈希表中的某数b，使得 target - a == b ，那么我们直接返回 {a,b} 即可。否则我们在哈希表中添加 a。时间复杂度 O(n)

//C++ 代码
class Solution {
public:vector<int> findNumbersWithSum(vector<int>& nums, int target) {unordered_map<int,int> hash;for(auto x : nums){if(hash[target-x] != 0) return {x,target-x};else hash[x]++;}return {-1,-1};}
};

---