面试经典 150 题 3 —（双指针）— 167. 两数之和 II - 输入有序数组

167. 两数之和 II - 输入有序数组

方法一

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        unordered_map<int,int> hashtable;
        for(int i = 1; i <= numbers.size(); i++){
            auto item = hashtable.find(target - numbers[i-1]);
            if(item != hashtable.end()){
                return {item->second,i};
            }
            hashtable[numbers[i-1]] = i;
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for(int i = 0; i < numbers.size(); i++){
            int low = i + 1, high = numbers.size() - 1;
            // 固定第一个数，二分法寻找第二个数，每次从右边开始
            while(low <= high){
                int mid = (high - low) / 2 + low;
                if(numbers[mid] == target - numbers[i]){
                    return {i+1, mid+1};
                }
                else if(numbers[mid] > target - numbers[i]){
                    high = mid - 1;
                }
                else{
                    low = mid + 1;
                }
            }
        }
        return {-1,-1};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

方法三

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