剑指offer57_和为S的两个数字

和为S的两个数字

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

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

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

数据范围

数组长度 [1,1002]。

样例

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

算法思路

(这就是leetcode第一题，没啥好说的，哈哈。)

核心思路是使用哈希表存储遍历过的数字，对于每个当前数字 x，检查哈希表中是否存在 target - x：

• 若存在，则找到答案，返回 {x, target - x}。
• 若不存在，则将当前数字 x 加入哈希表，继续遍历。

时间复杂度：

• O(n)：遍历数组一次（n 为数组长度），哈希表的插入和查找操作平均时间复杂度为 O(1)。

空间复杂度：

• O(n)：最坏情况下需要存储所有数组元素（哈希表大小与数组长度线性相关）。

class Solution {
public:vector<int> findNumbersWithSum(vector<int>& nums, int target) {// 使用哈希表存储已遍历的数字unordered_set<int> hash;for (auto x : nums) { // 遍历每个数字// 检查 target - x 是否在哈希表中if (hash.count(target - x)) {// 找到匹配：返回当前数字x和补数(target-x)return {x, target - x};}// 未找到匹配：将当前数字加入哈希表hash.insert(x);}// 未找到任何匹配（题目保证有解，此步可省略）return {};}
};

实例演示

假设输入数组 nums = [1, 2, 3, 4]，目标值 target = 6：

1. 遍历 x=1：
   • 检查 6-1=5 是否在哈希表 {} → 不存在
   • 插入 1 → 哈希表 {1}
2. 遍历 x=2：
   • 检查 6-2=4 是否在哈希表 {1} → 不存在
   • 插入 2 → 哈希表 {1, 2}
3. 遍历 x=3：
   • 检查 6-3=3 是否在哈希表 {1, 2} → 不存在
   • 插入 3 → 哈希表 {1, 2, 3}
4. 遍历 x=4：
   • 检查 6-4=2 是否在哈希表 {1, 2, 3} → 存在！
   • 返回结果 {4, 2}（顺序为 [x, target-x]）

最终输出：[4, 2]（满足 4+2=6）。