LeetCode 167. 两数之和 II - 输入有序数组
题目描述
思路分析
由于数组是有序的，我们可以使用双指针的方法来解决这个问题。具体思路如下：
初始化两个指针，
left指向数组的起始位置，right指向数组的末尾。计算 numbers[left] + numbers[right] 的和：
如果和等于
target，返回这两个指针的下标（加 1）。- 如果和小于
target，说明需要更大的数，将left向右移动。- 如果和大于
target，说明需要更小的数，将right向左移动。重复以上步骤，直到找到答案。
这种方法的优点是时间复杂度较低，适合处理有序数组。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func twoSum(numbers []int, target int) []int {
left, right := 0, len(numbers)-1
for left < right {
sum := numbers[left] + numbers[right]
if sum == target {
return []int{left + 1, right + 1}
} else if sum < target {
left++
} else {
right--
}
}
return []int{}
}
- 时间复杂度：O (n)，其中 n 是数组
numbers的长度。我们只遍历了一次数组。- 空间复杂度：O (1)，只使用了常数级别的额外空间。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！