LeetCode 167. 两数之和 II - 输入有序数组

题目描述

✅ 167. 两数之和 II - 输入有序数组

image-20230309213657371

思路分析

由于数组是有序的，我们可以使用双指针的方法来解决这个问题。

具体思路如下：

  1. 初始化两个指针，left 指向数组的起始位置，right 指向数组的末尾。

  2. 计算 numbers[left] + numbers[right] 的和：

    • 如果和等于 target，返回这两个指针的下标（加 1）。
    • 如果和小于 target，说明需要更大的数，将 left 向右移动。
    • 如果和大于 target，说明需要更小的数，将 right 向左移动。
  3. 重复以上步骤，直到找到答案。

参考代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14



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} // 返回索引从 1 开始
		} else if sum < target {
			left++ // 和小于目标值，左指针右移
		} else {
			right-- // 和大于目标值，右指针左移
		}
	}
	return nil
}
  • 时间复杂度：O(n)，其中 n 是数组的长度。
  • 空间复杂度：O(1)，我们只使用了常数级别的额外空间。

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2024/46257152
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！