DEV Community
·
两数之和
💡
原文英文，约300词，阅读约需1分钟。
📝
内容提要
给定一个整数数组和目标值，返回两个数的索引，使其和为目标值。假设每个输入有且仅有一个解，且不能重复使用元素。使用哈希表存储数组值及其索引，遍历数组计算目标值与当前值的差，如果哈希表中存在该差值，则返回对应索引。例如：[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。
❓
延伸问答
如何找到两个数的索引使其和为目标值？
使用哈希表存储数组值及其索引，遍历数组计算目标值与当前值的差，如果哈希表中存在该差值，则返回对应索引。
能否给出一个示例来说明如何实现这个算法？
例如，对于输入 nums = [2,7,11,15] 和目标值 9，返回的索引是 [0,1]，因为 nums[0] + nums[1] == 9。
这个算法的时间复杂度是多少？
该算法的时间复杂度为 O(n)，因为需要遍历数组一次。
在什么情况下这个算法会失败？
该算法假设每个输入有且仅有一个解，如果输入不满足这一条件，算法可能无法正确返回结果。
如何处理数组中有重复元素的情况？
算法允许使用不同的索引，即使数组中有重复元素，只要不重复使用同一个元素即可。
这个算法的实现语言是什么？
该算法的代码实现使用 Java 语言。
➡️
