题目描述

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

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

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

样例

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

算法1

STL

C++ 代码

class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        unordered_set<int> S;
        for (auto x : nums)
        {
            if (S.count(target - x)) return {x, target - x};
            S.insert(x); //维护哈希表，每次判断完将其加入到哈希表中
        }
        return vector<int> ();//保证解的规范（有解），需写构造函数
    }
};

算法2

双指针

C++ 代码

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

       }
    }   
};