深入解析力扣167题：两数之和 II（双指针法详解及模拟面试问答）

关注微信公众号 数据分析螺丝钉 免费领取价值万元的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。
1
2
3

示例 2:

输入: numbers = [2, 3, 4], target = 6
输出: [1, 3]
1
2

示例 3:

输入: numbers = [-1, 0], target = -1
输出: [1, 2]
1
2

解题思路

方法一：双指针法

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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复杂度分析

• 时间复杂度：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
• 力扣官方题解