本文题目难度标识：🟩简单，🟨中等，🟥困难。

热身：从「两数之和」问题铺垫

「两数之和」在 LeetCode 编号为 1，是题库的第一道题目。

题目：🟩 1. 两数之和 - 力扣（LeetCode）

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

暴力方法：最容易想到的方法，枚举数组中的每一个数 x，寻找数组中是否存在 target - x。

时间复杂度： $O(N^2)$ ，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
空间复杂度： $O(1)$ 。

哈希表：使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 $O(N)$ 降低到 $O(1)$ 。

时间复杂度： $O(N)$ ，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 $O(1)$ 地寻找 target - x。
空间复杂度： $O(N)$ ，其中 N 是数组中的元素数量。主要为哈希表的开销。

排序 + 双指针

题目：🟨 167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序 排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

我们可以使用上题「两数之和」中的方法解决，但是这道题的特点在于输入是一个有序的数组，我们可以利用这一点进行方法优化。官方解法有以下两种：

二分查找：首先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。利用数组的有序性质，可以通过二分查找的方法寻找第二个数。为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找。
- 时间复杂度： $O(n\log n)$ ，其中 n 是数组的长度。需要遍历数组一次确定第一个数，时间复杂度是 $O(n)$ ，寻找第二个数使用二分查找，时间复杂度是 O(\log n)，因此总时间复杂度是 $O(n\log n)$ 。
- 空间复杂度： $O(1)$ 。
双指针

下面主要介绍双指针方法。

初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。

如果两个元素之和等于目标值，则发现了唯一解。
如果两个元素之和小于目标值，则将左侧指针右移一位。
如果两个元素之和大于目标值，则将右侧指针左移一位。
移动指针之后，重复上述操作，直到找到答案。

复杂度分析：

时间复杂度： $O(n)$ ，其中 n 是数组的长度。两个指针移动的总次数最多为 n 次。
空间复杂度： $O(1)$ 。

双指针的理解

那么上面双指针会不会把可能的解过滤掉？答案是不会。「两数之和 II」中明确表示只存在唯一的答案。

理解方式 1：抓住了答案后不会错过

假设 numbers[i]+numbers[j]==target 是唯一解，其中 0≤i<j≤numbers.length−1。初始时两个指针分别指向下标 0 和下标 numbers.length−1，左指针指向的下标小于或等于 i，右指针指向的下标大于或等于 j。除非初始时左指针和右指针已经位于下标 i 和 j，否则一定是左指针先到达下标 i 的位置或者右指针先到达下标 j 的位置。

如果左指针先到达下标 i 的位置，此时右指针还在下标 j 的右侧，sum>target，因此一定是右指针左移，左指针不可能移到 i 的右侧。
如果右指针先到达下标 j 的位置，此时左指针还在下标 i 的左侧，sum<target，因此一定是左指针右移，右指针不可能移到 j 的左侧。

因此使用双指针一定可以找到答案。

理解方式 2：双指针是答案的边界

双指针还可以这样理解：双指针指示的范围表示答案可能出现的范围。

计算两个指针 left、right 指向的两个元素之和 nums[left]+nums[right]，如果两个元素之和等于目标值，则发现了唯一解。
如果两个元素之和小于目标值 nums[left]+nums[right]<target，说明左侧指针指向的值 nums[left] 不可能作为答案。因为 nums[left] 和答案范围内所有其他的数相加，总会有 nums[left]+nums[k]<target，left<k<right，因此需要将左侧指针右移一位，缩短答案范围。
如果两个元素之和大于目标值，则将右侧指针左移一位。原因同上。
当左右指针正好指向正确答案时返回结果即可。