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

输入一个数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。

如果有多对数字的和等于 s，输出任意一对即可。

你可以认为每组输入中都至少含有一组满足条件的输出。
样例

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

输出：[3,4]

分析：
算法一：
暴力穷举

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

算法二：
开一个Hash表，快速寻找数组中是否存在目标元素。如果存在，[x, target - x] 即为答案。

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从降低到 。

创建一个哈希表，对于每一个，我们首先查询哈希表中是否存在，如果有返回。如果没有，将 x 插入到哈希表中。

时间复杂度： 空间复杂度：

class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for(auto x:nums)
            if(hash[target-x]) return {x, target-x};
            else hash[x]++;
    }
};

算法三：
双指针算法
首先要排序一下，排序的时间复杂度是,双指针扫描时间复杂度是
所以，总时间复杂度是

class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());//时间复杂度NlogN
        //双指针算法
        for(int i=0, j = nums.size()-1; i<j;)
            if(nums[i] + nums[j] == target) return {nums[i], nums[j]};
            else if(nums[i] + nums[j] < target) i++;
            else j--;
    }
};