[剑指 Offer 57. 和为s的两个数字]

[剑指 Offer 57. 和为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]

限制：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6

方法1：使用2分法进行查找

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            int temp = target - nums[i];
            int left = i+1;
            int right = nums.size() - 1;
            while(left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[temp] < nums[mid]) {
                    right = mid - 1;
                } else if (nums[temp] > nums[mid]) {
                    left = mid + 1;
                } else if (nums[temp] == nums[mid]) {
                    return { nums[temp], nums[mid] };
                }
            }
        }
        return { 0, 0 };
    }
};

方法2：使用hash表，如果target-nums[i]在表中可以查找得到，就可以直接返回结果{target-nums[i],nums[i]}，否则就将结果存储在hash表中

class Solution {
public:
    unordered_set<int>hash;

public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            int val = target - nums[i];
            if (hash.count(val) != 0) {
                return {val,nums[i]};
            } else {
                hash.insert(nums[i]);
            }
        }
        return { 0, 0 };
    }
};

方法3：利用数组排好序的特点，使用双指针的方式

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while(left < right) {
            int val = nums[left] + nums[right];
            if(val == target) {
                return {nums[left],nums[right]};
            } else if (val > target) {
                right--;
            } else if (val < target) {
                left++;
            }
        }
        return { 0, 0 };
    }
};