LeetCode-剑指57-和为s的两个数字

1、二分查找

我们对于每一个数，都在数组中二分查找其对应的值，若存在则直接返回。

class Solution {
public:
    int binarySearch(vector<int> &nums, int low, int high, int target) {
        if (low > high) return -1;
        int mid = (low + high) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] > target) return binarySearch(nums, low, mid - 1, target);
        else return binarySearch(nums, mid + 1, high, target);
    }

    vector<int> twoSum(vector<int> &nums, int target) {
        int n = nums.size();
        for (int i: nums) {
            int index = binarySearch(nums, 0, n - 1, target - i);
            if (index != -1)
                return {i, nums[index]};
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2、双指针

我们可以使用双指针分贝指向数组开头和结尾：1、当$nums[low]+nums[high]==target$时说明当前即为题目所需要的解，我们直接返回数组；2、当$nums[low]+nums[high]>target$时说明当前两个指针指向元素之和大于目标值，我们可以将右指针左移从而减少和的大小；3、当$nums[low]+nums[high]<target$时说明当前两个指针指向元素之和小于目标值，我们可以将左指针右移从而增大和的大小。

class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target) {
        int low = 0, high = nums.size() - 1;
        while (low < high) {
            if (nums[low] + nums[high] == target) return {nums[low], nums[high]};
            else if (nums[low] + nums[high] > target) --high;
            else ++low;
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12