【面试经典150 | 双指针】两数之和

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【双指针】【二分法】【哈希表】【数组】

---

题目来源

面试经典150 | 167. 两数之和 II - 输入有序数组

---

题目解读

给定一个下标从 1 开始按照 非递减顺序排列 的整数数组 numbers，找出两数之和等于 target 的两个数，返回它们的下标，其中每个整数只能使用一次，题目保证只有唯一的答案。

---

解题思路

本题属于基础题，与 1. 两数之和 解法基本一致。现在有三种解法如下。

方法一：暴力枚举

一个比较容易想到的方法就是枚举所有可能的两数组合，使用两层枚举，第一层枚举第一个整数，第二层枚举第二个整数。本题的数据量为 $10^4$，两层枚举的时间复杂度为 $10^8$，勉强可以通过。

具体地，在枚举中判断两数之和是否等于 target，如果相等，直接返回对应的下标。

因为每个元素只可以使用一次，并且两数先后出现的顺序没有要求，因此
第二层枚举的整数可以从第一层枚举的整数的后一个位置开始。

实现代码

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                if (numbers[i] + numbers[j] == target) {
                    return {i + 1, j + 1};
                }
            }
        }
        return {-1, -1};    // 本题保证一定有解，程序不会运行到此处
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

但是实测中，最后几个测试用例超时了！

复杂度分析

时间复杂度：$O(n^2)$。

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

方法二：哈希表

方法一中的时间复杂度可以优化到 $O(nlogn)$ 和 $O(n)$，先来介绍时间复杂度为 $O(n)$ 的方法，时间复杂度为 $O(nlogn)$ 的方法将在方法三中介绍。

我们在枚举第二个整数的时候，可以事先用一个哈希表来记录下所有整数以及位置，这样枚举第二个整数的时间复杂度可以降为 $O(1)$，但是需要一个额外的空间。

具体地，可以先一次遍历 numbers，记录每个整数以及下标；记录完毕后，枚举第一个加数，在哈希表中查找第二个加数；以上的过程可以用一个循环就可以解决：枚举第一个加数之后，先在哈希表中查询有么有合适的第二个加数，然后再将当前的加数放入哈希表中，这样可以省去一次 for 循环。

实现代码

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

复杂度分析

时间复杂度：$O(n)$，$n$ 为数组 numbers 的长度，只要一次循环就可以枚举两个加数。

空间复杂度：$O(n)$，记录整数以及位置所用的空间。

方法三：二分法

在方法二中，我们是利用哈希表来降低枚举的线性时间的，我们还可以使用二分方法来降低线性枚举的时间复杂度。

前面两种方法中，都没有用到题目中 非递减顺序排列 这一条件，我们可以利用这种有序性进行二分查找第二个加数。

具体地，枚举第一个加数，假设下标为 i，接着要在 numbers[i+1,...,n-1] 中使用二分法查找 target - numbers[i]，如果查找到直接返回两个加数的对应下标，否则继续枚举第一个数查找。

实现代码

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

复杂度分析

时间复杂度：$O(nlogn)$，枚举第一个数的时间复杂度为 $O(n)$，在每次枚举中最坏需要二分查找 O(logn) 次，才能找到合适的第二个加数。

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

方法四：双指针

以上三种都不是最优的，现在介绍时间复杂度和空间复杂度都是最优的方法——双指针。

初始左右两个指针 $left$ 和 $right$ 分别指向 numbers 的第一个位置和最后一个位置。每次计算两个指针指向的整数之和，与 target 进行比较：

• 如果 numbers[left] + numbers[right] = target，直接返回 {left + 1, right + 1}（因为下标从 1 开始）；
• 如果 numbers[left] + numbers[right] > target，则将 right 指针左移一位；
• 如果 numbers[left] + numbers[right] < target，则将 left 指针右移移位。

为什么两数之和小了，右移 left 就可以了，右移 right 不可以吗？为什么两数之和大了，左移 right 就可以了，左移 left 不可以吗？

假设 numbers[i] + numbers[j] = target 是唯一解，其中 0 <= i < j <= n-1。初始时 left = 0、right = n-1，除非初始的时候，左右两个指针已经位于 i、j 处，否则一定是左指针先到达下标 i，或者右指针先到达下标 j：

• 左指针先到达下标 i 时，右指针还在 j 的右侧，此时 numbers[left] + numbers[right] > target，于是需要将 right 指针左移一位，这样才能缩小两数之和；
• 右指针先到达下标 j时，左指针还在 i 的左侧，此时 numbers[left] + numbers[right] < target，于是需要将 left 指针右移一位，这样才能增加两数之和。

于是，就有了以上所示的双指针更新规则。

实现代码

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        int l = 0, r = n - 1;
        while (l <= r) {
            int sum = numbers[l] + numbers[r];
            if (sum > target) {
                --r;
            }
            else if (sum < target) {
                ++l;
            }
            else {
                return {l+1, r+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

复杂度分析

时间复杂度：$O(n)$，双指针相向移动，它们 一共最多走 n 次。

空间复杂度：$O(1)$，使用的额外变量只有两个指针。

---

知识回顾

今天来看看 $\text{C++}$ 中二分查找的几个 API。

find() 使用二分法来查找数组中指定值的位置，其返回的是迭代器：

• 如果顺利查找到指定元素，则返回该元素位置迭代器；
• 如果没有查找到指定元素，则返回尾后迭代器；

通过位置迭代器与首位置迭代器作差可以得到该元素在数组中的位置。

lower_bound() 和 upper_bound() 的含义与用法可以参考 【二分查找】几种基本题型，你会了吗？。

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。