力扣经典150题第二十七题：两数之和 II - 输入有序数组

力扣经典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. 解题思路

由于数组已经按非递减顺序排列，我们可以利用双指针技巧来解决这个问题：

1. 使用两个指针 left 和 right 分别指向数组的头部和尾部。
2. 如果指针 left 和 right 所指向的元素之和等于 target，则返回它们的下标。
3. 如果指针 left 和 right 所指向的元素之和小于 target，则将 left 右移一位。
4. 如果指针 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 官方网站
• 《算法导论》
• 《程序员面试金典》

感谢阅读

期待下一篇…