Ex57 和为s的两个数字

题目描述

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

解题思路

使用双指针解法。因为这是一个递增排序的数组，设置low指针为数组的第一个数，即数组中最小的数，设置high指针为数组的最后一个数，即数组中最大的数。当这两数相加，如果小于target，则将low向增加；如果大于target，则将high减小。

代码

class Solution {
 public:
  std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::vector<int> res;
    if (nums.size() < 2) return res;
    decltype(nums.size()) low = 0, high = nums.size() - 1;
    while (low < high) {
      int low_num = nums[low], high_num = nums[high];
      if (target == low_num + high_num) {
        res.push_back(low_num);
        res.push_back(high_num);
        return res;
      } else if (target < low_num + high_num) {
        --high;
      } else {
        ++low;
      }
    }
    return res;
  }
};

结果

执行结果：通过

执行用时：420 ms, 在所有 C++ 提交中击败了57.22%的用户

内存消耗：98.5 MB, 在所有 C++ 提交中击败了58.12%的用户