关注微信公众号 数据分析螺丝钉 免费领取价值万元的python/java/商业分析/数据结构与算法学习资料
在本篇文章中，我们将详细解读力扣第167题“两数之和 II - 输入有序数组”。通过学习本篇文章，读者将掌握如何使用多种方法来解决这一问题，并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释和ASCII图解，以便于理解。
问题描述
力扣第167题“两数之和 II - 输入有序数组”描述如下：
给定一个已按照升序排列的整数数组
numbers，请你从数组中找出两个数，使得它们的和等于目标数target。函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例 1:
输入: numbers = [2, 7, 11, 15], target = 9 输出: [1, 2] 解释: 2 与 7 之和等于目标数 9。因此 index1 = 1, index2 = 2。
示例 2:
输入: numbers = [2, 3, 4], target = 6 输出: [1, 3]
示例 3:
输入: numbers = [-1, 0], target = -1 输出: [1, 2]
解题思路
方法一：双指针法
- 初步分析：
- 由于数组是有序的，可以使用双指针法高效地找到两个数，使它们的和等于目标数。
- 步骤：
- 初始化两个指针，
left指向数组的起始位置，right指向数组的末尾。 - 计算
numbers[left]和numbers[right]的和，如果和等于目标数，则返回两个指针的索引。 - 如果和小于目标数，移动左指针
left向右。 - 如果和大于目标数，移动右指针
right向左。
代码实现
def twoSum(numbers, target): left, right = 0, len(numbers) - 1 while left < right: current_sum = numbers[left] + numbers[right] if current_sum == target: return [left + 1, right + 1] elif current_sum < target: left += 1 else: right -= 1 return [] # 测试案例 print(twoSum([2, 7, 11, 15], 9)) # 输出: [1, 2] print(twoSum([2, 3, 4], 6)) # 输出: [1, 3] print(twoSum([-1, 0], -1)) # 输出: [1, 2]
ASCII图解
假设输入为 numbers = [2, 7, 11, 15] 和 target = 9，图解如下：
初始化指针: left = 0, right = 3 第一次比较: numbers[left] + numbers[right] = 2 + 15 = 17 > 9 移动右指针: left = 0, right = 2 第二次比较: numbers[left] + numbers[right] = 2 + 11 = 13 > 9 移动右指针: left = 0, right = 1 第三次比较: numbers[left] + numbers[right] = 2 + 7 = 9 == 9 找到目标: 返回 [1, 2]
复杂度分析
- 时间复杂度：O(n)，其中 n 是数组的长度。只需遍历一次数组。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。
模拟面试问答
问题 1：你能描述一下如何解决这个问题的思路吗？
回答：我们需要在有序数组中找到两个数，使它们的和等于目标数。可以使用双指针法：初始化两个指针，分别指向数组的起始位置和末尾位置。计算两个指针指向的数的和，如果和等于目标数，则返回指针的索引；如果和小于目标数，移动左指针；如果和大于目标数，移动右指针。如此循环，直到找到目标数。
问题 2：为什么选择使用双指针法？
回答：由于数组是有序的，使用双指针法可以高效地找到两个数的组合。双指针法的时间复杂度是 O(n)，比暴力搜索的 O(n^2) 更高效。
问题 3：你的算法如何处理重复元素？
回答：由于每个输入只对应唯一的答案，所以算法会找到两个数和等于目标数时直接返回结果，不需要考虑重复元素的问题。算法中的比较和移动指针的操作确保了不会重复使用相同的元素。
问题 4：如何处理数组长度小于2的情况？
回答：如果数组长度小于2，不可能找到两个数和等于目标数。可以在算法开始时检查数组长度，如果小于2，直接返回空列表。
问题 5：你能解释一下双指针法的工作原理吗？
回答：双指针法通过初始化两个指针，分别指向数组的起始位置和末尾位置。计算两个指针指向的数的和，如果和等于目标数，则返回指针的索引；如果和小于目标数，移动左指针；如果和大于目标数，移动右指针。这样通过逐步缩小范围，找到目标数。
问题 6：在代码中如何确保返回的索引是从1开始的？
回答：在代码中，返回结果时将指针的索引加1。例如，return [left + 1, right + 1]。这样确保返回的索引是从1开始的，而不是从0开始的。
问题 7：如果数组中没有符合条件的两个数，算法会如何处理？
回答：如果数组中没有符合条件的两个数，算法会在循环结束后返回空列表 []，表示没有找到符合条件的两个数。
问题 8：你能举例说明在面试中如何回答优化问题吗？
回答：在面试中，如果面试官问到如何优化算法，我会首先分析当前算法的瓶颈，如时间复杂度和空间复杂度，然后提出优化方案。例如，对于“两数之和 II - 输入有序数组”问题，使用双指针法可以将时间复杂度优化到 O(n)，比暴力搜索更高效。
问题 9：如何验证代码的正确性？
回答：通过多个测试案例验证代码的正确性，包括正常情况和边界情况。例如，测试数组长度小于2的情况，目标数为数组中不存在的情况，数组中有负数的情况等，确保代码在各种情况下都能正确运行。
问题 10：你能解释一下双指针法的适用场景吗？
回答：双指针法适用于有序数组或链表的情况，可以高效地解决查找问题。例如，查找两个数和等于目标数的问题、查找连续子数组和等于目标数的问题等。通过双指针法，可以在 O(n) 时间复杂度内找到答案，比暴力搜索更高效。
总结
本文详细解读了力扣第167题“两数之和 II - 输入有序数组”，通过双指针法高效地解决了这一问题，并提供了详细的ASCII图解和模拟面试问答。希望读者通过本文的学习，能够在力扣刷题的过程中更加得心应手。
参考资料
- 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- 力扣官方题解
欢迎关注微信公众号 数据分析螺丝钉
