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

记录了一道LeetCode题的解法。

一开始我使用的是经典的哈希表解法：

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

时间复杂度为$O(n)$，空间复杂度也为$O(n)$，但是题目要求“必须只使用常量级的额外空间”，因此该解法不符合要求。

以下双指针和二分法符合题目的要求。

双指针

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

• 时间复杂度为$O(n)$。
• 空间复杂度为$O(1)$。

二分查找

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for (int i = 0; i < numbers.size(); i ++) {
            int diff = target - numbers[i];
            int l = i + 1, r = numbers.size() - 1;
            int mid;
            while (l < r) {
                mid = l + r >> 1;
                if (numbers[mid] >= diff) r = mid;
                else l = mid + 1;
            }
            if (numbers[l] == diff)
                return {i + 1, l + 1};
        }
        return {-1, -1};
    }
};

• 时间复杂度：$O(n \log n)O(n\log n)$，其中 $n$ 是数组的长度。需要遍历数组一次确定第一个数，时间复杂度是$O(n)O(n)$，寻找第二个数使用二分查找，时间复杂度是 $O(\log n)O(\log n)$，因此总时间复杂度是 $O(n\log n)O(n\log n)$。

• 空间复杂度：$O(1)$。