【LeetCode.167】Two Sum II - Input array is sorted （C++）

落日映苍穹つ 2022-02-05 12:49 96阅读 0赞

# 问题描述 #

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

*  Your returned answers (both index1 and index2) are not zero-based.
 *  You may assume that each input would have exactly one solution and you may not use the same element twice.

索引从1开始的。

# 示例 #

Input: numbers = \[2,7,11,15\], target = 9  
Output: \[1,2\]  
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

# 哈希表 #

class Solution { 
    public:
        vector<int> twoSum(vector<int>& nums, int target) { 
            vector<int> res;
            map<int,int> hash;
            for(int i=0;i<nums.size();i++){ 
                if(hash.find(target-nums[i]) != hash.end()){ 
                    //因为要寻找差值，所以key必须存数，而不是索引
                    res.push_back(hash[ target-nums[i] ]+1);//已存在的肯定索引小，先加入
                    res.push_back(i+1);
                    return res;
                }
                hash[nums[i]] = i;
            }
            return res;
        }
    };

好像没什么好说，方法和Two Sum一样。

# 双向扫描法 #

class Solution { 
    public:
        vector<int> twoSum(vector<int>& numbers, int target) { 
            int i = 0, j = numbers.size() - 1;
            while (i < j) { 
                int sum = numbers[i] + numbers[j];
                if (sum > target)
                    j--;
                else if (sum < target)
                    i++;
                else
                    return { i + 1, j + 1};//索引从1开始的
            }
            return { };
        }
    };

好像也没什么好说。看之前的博客吧。