力扣经典150题解析之二十七：两数之和 II - 输入有序数组
1. 介绍
在这篇文章中，我们将解析力扣经典150题中的第二十六题：两数之和 II - 输入有序数组。题目要求在一个已按非递减顺序排列的整数数组中，找出两个数的和等于目标数 target，并返回它们的下标。
2. 问题描述
给定一个下标从1开始的整数数组 numbers，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。返回这两个整数的下标，其中 1 <= index1 < index2 <= numbers.length。
3. 示例
示例 1:
输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 + 7 = 9，因此 index1 = 1, index2 = 2。返回 [1, 2]。
示例 2:
输入：numbers = [2,3,4], target = 6 输出：[1,3] 解释：2 + 4 = 6，因此 index1 = 1, index2 = 3。返回 [1, 3]。
示例 3:
输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 + 0 = -1，因此 index1 = 1, index2 = 2。返回 [1, 2]。
4. 解题思路
由于数组已经按非递减顺序排列，我们可以利用双指针技巧来解决这个问题：
- 使用两个指针 left 和 right 分别指向数组的头部和尾部。
- 如果指针 left 和 right 所指向的元素之和等于 target，则返回它们的下标。
- 如果指针 left 和 right 所指向的元素之和小于 target，则将 left 右移一位。
- 如果指针 left 和 right 所指向的元素之和大于 target，则将 right 左移一位。
5. 算法实现
public int[] twoSum(int[] numbers, int target) { int left = 0, right = numbers.length - 1; while (left < right) { int sum = numbers[left] + numbers[right]; if (sum == target) { return new int[] {left + 1, right + 1}; // 返回下标，注意下标从1开始 } else if (sum < target) { left++; } else { right--; } } return new int[] {-1, -1}; // 未找到满足条件的情况 }
6. 复杂度分析
- 时间复杂度：O(n)，其中 n 是数组 numbers 的长度。双指针遍历一次数组。
- 空间复杂度：O(1)，只使用了常数级的额外空间。
7. 测试与验证
测试用例设计
- 输入数组长度为2，包含两个元素满足条件。
- 输入数组长度为3，包含三个元素满足条件。
- 输入数组长度为4，找不到满足条件的两个元素。
测试结果分析
根据不同的测试用例，分析算法的输出结果，验证解决方案的正确性和有效性。
8. 总结
通过双指针法，我们可以高效地在有序数组中找出两个数的和等于目标数 target，并返回它们的下标。本文详细介绍了解题思路、算法实现和复杂度分析，希望对读者理解该问题和解决方法有所帮助。
9. 参考文献
- LeetCode 官方网站
- 《算法导论》
- 《程序员面试金典》
感谢阅读
期待下一篇…
