注意这题结果 index 从 1 开始
Solution1 遍历 + 二分查找
时间复杂度 $O(n * logn)$
空间复杂度 $O(1)$
需要索引是有序的。（其实按照 two sum 的做法，再排下序也可以....）
Solution2 双指针
时间复杂度 $O(n)$
l 和 r 最多总共移动 n 次
空间复杂度 $O(1)$
可以证明，对于排好序且有解的数组，双指针一定能遍历到最优解。证明方法如下：假设最 优解的两个数的位置分别是 l 和 r。我们假设在左指针在 l 左边的时候，右指针已经移动到了 r； 此时两个指针指向值的和小于给定值，因此左指针会一直右移直到到达 l。同理，如果我们假设 在右指针在 r 右边的时候，左指针已经移动到了 l；此时两个指针指向值的和大于给定值，因此 右指针会一直左移直到到达 r。所以双指针在任何时候都不可能处于 (l,r) 之间，又因为不满足条件时指针必须移动一个，所以最终一定会收敛在 l 和 r。
Last updated