跳转至

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

如果仿效1 两数之和,也能过。但是题目要求空间复杂度为\(O(1)\)这种做法显然不满足

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        unordered_map<int,int> hashMap;
        for(int i = 0; i < numbers.size(); i++){
            int sum = target - numbers[i];
            if(hashMap.count(sum)){
                return {hashMap[sum], i + 1};
            }
            hashMap[numbers[i]] = i + 1;
        }
        return {};
    }
};

既然都给了排序,那么我们不需要使用哈希表了,直接使用双指针就可以了

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        // 不能使用两次相同元素, left == right不能成立
        while(left < right){
            if(numbers[left] + numbers[right] == target){
                return {left + 1, right + 1};
            }else if(numbers[left] + numbers[right] < target){
                left++;
            }else if(numbers[left] + numbers[right] > target){
                right--;
            }
        }
        return {};
    }
};