【leetcode】21. 序列-和为s的两个数字

发表于 更新于 分类于 阅读次数： 本文字数： 1k 阅读时长 ≈ 1 分钟

题目

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

示例 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/problems/he-wei-sde-liang-ge-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

分析

本题和《【leetcode】5. 数组-两数之和》列数，不通的地方是本题给出的数组是递增有序的。因此可以利用这条件来进行优化求解。
基本方法是利用双指针法，遍历求和。设有两个指针（下标）int left = 0, right = nums.size() - 1; 循环求解um = nums[left] + nums[right];

  1. 如果 sum == target 则返回对应下标元素
  2. 如果 sum < target 则left++
  3. 否则 rigth--

时间复杂度：O(N)
空间复杂度：O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        vector<int> res;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                res.push_back(nums[left]);
                res.push_back(nums[right]);
                return res;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }
};