和为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]

解法

解法一：

思路：

• 利用 HashMap 可以通过遍历数组找到数字组合，时间和空间复杂度均为 O(N)；
• 注意本题的 nums 是 排序数组 ，因此可使用 双指针法 将空间复杂度降低至 O(1) 。

算法流程：

1. 初始化： 双指针 i , j 分别指向数组 nums的左右两端 （俗称对撞双指针）。

2. 循环搜索： 当双指针相遇时跳出；

   计算和 s=nums[i]+nums[j]；
   若 s>target ，则指针 j 向左移动，即执行 j=j−1 ；
   若 s<target，则指针 i 向右移动，即执行 i=i+1 ；
   若 s=target ，立即返回数组 [nums[i],nums[j]]；

3. 返回空数组，代表无和为 target的数字组合。

代码：

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

知识点

1. 双指针（对撞指针）。