关于leetcode:每日一练29和为s的两个数字

title: 每日一练（29）：和为 s 的两个数字

categories:[剑指 offer]

tags:[每日一练]

date: 2022/03/02

每日一练（29）：和为 s 的两个数字

输出一个递增排序的数组和一个数字 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

起源：力扣（LeetCode）

链接：https://leetcode-cn.com/probl…

办法一：哈希

思路：

• 创立哈希表
• 遍历数组
• 若哈希表中存在元素与以后遍历到的元素之和为 target 则返回后果即可
• 没有满足条件的元素，返回空

vector<int> twoSum(vector<int>& nums, int target) {
    // 创立哈希表
    unordered_set<int> s;
    // 遍历数组
    for (int x : nums) {
        // 若哈希表中存在元素与以后遍历到的元素之和为 target
        // 则返回后果即可
        if (s.count(target - x)) {return vector<int>{x, target - x};
        }
        // 插入以后遍历到的元素
        s.insert(x);
    }
    // 没有满足条件的元素，返回空
    return {};}

办法二：双指针

充分利用递增数组的性质，双指针从头尾开始遍历，两数和小于指标，则 left++；大于指标，则 right–。

vector<int> twoSum(vector<int>& nums, int target) {int l = 0; int r = nums.size() - 1;
    while (l < r) {if (target == nums[l] + nums[r]) {return vector<int>{nums[l], nums[r]};
        }
        else if (target > nums[l] + nums[r]) {l++;}
        else if (target < nums[l] + nums[r]) {r--;}
    }
    return vector<int>();}