What is the best way to solve Two Sum II - Input Array Is Sorted?

The optimal way is to use the two-pointer technique, achieving O(n) time complexity. Alternatively, you can use binary search for O(n log n) time complexity.

Can I solve this problem with brute force?

Yes, but brute force results in O(n^2) time complexity, which is inefficient for larger arrays. A more efficient solution is required for large input sizes.

Why is binary search useful in this problem?

Binary search takes advantage of the sorted nature of the array, enabling faster searching for the complement of each element.

How does the two-pointer technique work here?

The two-pointer technique works by starting with pointers at both ends of the sorted array. You adjust the pointers based on the sum of the elements they point to, ensuring you efficiently find the pair that sums to the target.

What happens if the array is not sorted?

If the array is not sorted, binary search and the two-pointer technique cannot be used. You would likely need to use a hash map or other sorting-based methods.

#167

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

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

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index 1 ] 和 numbers[index 2 ] ，则 1 1 2 。以长度为 2 的整数数组 [in…

数组双指针二分查找

题目描述

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

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

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

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

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index₁ = 1, index₂ = 2 。返回 [1, 2] 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index₁ = 1, index₂ = 3 。返回 [1, 3] 。

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index₁ = 1, index₂ = 2 。返回 [1, 2] 。

提示：

2 <= numbers.length <= 3 * 10⁴
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案

lightbulb

解题思路

方法一：二分查找

我们注意到数组按照非递减顺序排列，因此对于每个 $numbers[i]$ ，可以通过二分查找的方式找到 $target - numbers[i]$ 的位置，如果存在，那么返回 $[i + 1, j + 1]$ 即可。

时间复杂度 $O(n \times \log n)$ ，其中 $n$ 为数组 $numbers$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        for i in range(n - 1):
            x = target - numbers[i]
            j = bisect_left(numbers, x, lo=i + 1)
            if j < n and numbers[j] == x:
                return [i + 1, j + 1]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidates should understand the benefits of applying binary search to a sorted array.
question_mark
Look for understanding of the two-pointer technique and when it is most useful.
question_mark
The candidate should be able to discuss the space-time trade-offs between the different approaches.

warning

常见陷阱

外企场景

error
Failing to recognize that the array is sorted, which leads to inefficient brute-force solutions.
error
Not considering edge cases such as negative numbers or arrays with only two elements.
error
Mixing up index-based positions with 0-indexed arrays—make sure indices are 1-based.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array is not sorted? The problem would require different approaches like using a hash map.
arrow_right_alt
How would you solve the problem if there were multiple pairs that sum to the target? You’d need to modify your approach to find all pairs.
arrow_right_alt
How would this problem change if the array contained repeated elements? You would need to ensure that no element is used more than once.

help

常见问题

外企场景

继续练习

#287 寻找重复数 #349 两个数组的交集 #350 两个数组的交集 II