剑指 Offer 57. 和为s的两个数字 - 力扣（LeetCode）
就是两数之和嘛
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> m; for(const auto &num : nums){ int val = target - num; if(m.count(val)) return {val, m[val]}; else m[num] = val; } return {}; } };不过这题还有一个条件就是：数组是递增排序的，所以使用哈希表按照两数之和的思路并不是最优解。使用双指针从两边向中间遍历：
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int i = 0, j = nums.size()-1; while(i < j){ if(nums[i] + nums[j] == target) return {nums[i], nums[j]}; else if(nums[i] + nums[j] > target) --j;//左边界不变，调整右边界 else ++i;//右边界不变，调整左边界 } return {}; } };当然双指针的复杂度还是O(n)，提到递增的排序可以使用二分，但是这题的二分不太好应用，不过可以先二分查询target/2的位置，然后从中间向两边走：
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { //这儿是(traget+1)/2，向上取整 int mid = lower_bound(nums.begin(), nums.end(), (target+1)/2) - nums.begin(); int l = mid-1, r = mid; while(l >= 0 && r < nums.size()){ if(nums[l] + nums[r] == target) return {nums[l], nums[r]}; else if(nums[l] + nums[r] > target)//右边界不变，调整左边界 --l; else//左边界不变，调整右边界 ++r; } return {}; } };也可以遍历的时候对每一个元素二分，不过感觉还不如双指针。
