DEV Community
·
两数之和
内容提要
给定一个整数数组和目标值，返回两个数的索引，使其和为目标值。假设每个输入有且仅有一个解，且不能重复使用元素。使用哈希表存储数组值及其索引，遍历数组计算目标值与当前值的差，如果哈希表中存在该差值，则返回对应索引。例如：[2,7,11,15]目标9返回[0,1]。代码实现使用Java。
关键要点
-
给定一个整数数组和目标值，返回两个数的索引，使其和为目标值。
-
假设每个输入有且仅有一个解，且不能重复使用元素。
-
使用哈希表存储数组值及其索引。
-
遍历数组计算目标值与当前值的差。
-
如果哈希表中存在该差值，则返回对应索引。
-
示例1: 输入: nums = [2,7,11,15], target = 9 输出: [0,1]
-
示例2: 输入: nums = [3,2,4], target = 6 输出: [1,2]
-
示例3: 输入: nums = [3,3], target = 6 输出: [0,1]
-
约束条件: 2 <= nums.length <= 104，-10^9 <= nums[i] <= 10^9，-10^9 <= target <= 10^9。
-
初始化空哈希表，哈希表将包含数组中的值及其索引。
-
遍历数组，计算目标值与当前值的差，如果哈希表包含该差值，则返回索引。
-
代码实现使用Java。
延伸解读
哈希表的优势
使用哈希表存储数组值及其索引，可以在遍历过程中快速查找目标值的差值。这种方法的时间复杂度为O(n)，相比于暴力解法O(n^2)大大提高了效率，适合处理较大的数据集。
输入约束的重要性
文章中提到的输入约束（如数组长度和数值范围）对算法的设计至关重要。确保输入符合这些约束，可以避免潜在的错误和性能问题，尤其是在处理边界情况时。
代码实现的灵活性
虽然示例代码使用Java实现，但该算法的逻辑可以轻松迁移到其他编程语言中。理解算法的核心思想后，读者可以根据自己的需求选择合适的语言进行实现。
延伸问答
如何找到两个数的索引使其和为目标值？
使用哈希表存储数组值及其索引，遍历数组计算目标值与当前值的差，如果哈希表中存在该差值，则返回对应索引。
能否给出一个示例来说明如何实现这个算法？
例如，对于输入 nums = [2,7,11,15] 和目标值 9，返回的索引是 [0,1]，因为 nums[0] + nums[1] == 9。
这个算法的时间复杂度是多少？
该算法的时间复杂度为 O(n)，因为需要遍历数组一次。
在什么情况下这个算法会失败？
该算法假设每个输入有且仅有一个解，如果输入不满足这一条件，算法可能无法正确返回结果。
如何处理数组中有重复元素的情况？
算法允许使用不同的索引，即使数组中有重复元素，只要不重复使用同一个元素即可。
这个算法的实现语言是什么？
该算法的代码实现使用 Java 语言。
