题目描述

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

示例 2：

输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

限制：

• $1 <= nums.length <= 10^5$
• $1 <= nums[i] <= 10^6$

---

算法

(哈希表) $O(n)$

遍历数组，用哈希表存储每个元素以及出现次数，如果 $target - nums[i]$ 在哈希表中存在，那么数组中和为目标值 $target$ 的两个数就是 $target - nums[i]、nums[i]$。

时间复杂度

遍历一次数组的时间是 $O(n)$ 的，哈希表的操作是 $O(1)$ 的，所以总时间复杂度为 $O(n)$

空间复杂度

需要额外 $O(n)$ 的空间用于哈希表存储 $nums$ 中每个元素及出现次数。

C++ 代码

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