剑指57：和为s的两个数字

传送门

nowcoder
leetcode

题目描述

输入一个升序数组和一个数字，在数组中查找两个数，使得他们的和正好是S。
如果有多对数字的和等于S，返回任意一组即可；
如果无法找出这样的数字，返回一个空数组即可。

C++ 代码 - nowcoder

/*
    双指针：指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历
*/
class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> arr, int sum) {
        if (arr.size() == 0) return vector<int> {};

        vector<int> res;
        int low = 0, high = arr.size() - 1;
        while (low <= high) {
            int curSum = arr[low] + arr[high];
            if (curSum == sum) {
                res.push_back(arr[low]);
                res.push_back(arr[high]);
                return res;
            } else if (curSum < sum) {
                low ++;
            } else {
                high --;
            }
        }

        return res;
    }
};

C++ 代码 - leetcode

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 双指针：左右
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum < target) {
                left ++;  // 增大
            } else if (sum > target) {
                right --; // 减小
            } else {
                return { nums[left], nums[right] }; // 找到
            }
        }

        return {};
    }
};