DEV Community
·
1. 两数之和 || 数据结构与算法 || JavaScript || 作者：Munisekhar Udavalapati
💡
原文英文，约200词，阅读约需1分钟。
📝
内容提要
给定一个整数数组和目标值，返回两个数的索引，使它们的和等于目标值。假设每个输入都有唯一解，且不能重复使用同一元素。可以优化算法以降低时间复杂度。
🎯
关键要点
- 给定一个整数数组和目标值，返回两个数的索引，使它们的和等于目标值。
- 假设每个输入都有唯一解，且不能重复使用同一元素。
- 可以返回答案的顺序不固定。
- 示例1：输入为[2,7,11,15]，目标值为9，输出为[0,1]。
- 示例2：输入为[3,2,4]，目标值为6，输出为[1,2]。
- 示例3：输入为[3,3]，目标值为6，输出为[0,1]。
- 约束条件：数组长度在2到104之间，元素和目标值范围在-10^9到10^9之间。
- 存在唯一有效答案。
- O(n²)的算法实现：使用双重循环查找两个数的和。
- O(n)的优化算法实现：使用哈希表存储已遍历的元素，降低时间复杂度。
❓
延伸问答
如何找到两个数的索引使其和等于目标值？
可以使用双重循环遍历数组，检查每对数的和是否等于目标值，或使用哈希表优化算法以降低时间复杂度。
给定数组[2,7,11,15]和目标值9，输出是什么？
[0,1]，因为nums[0] + nums[1] == 9。
这个问题的输入有什么限制？
数组长度在2到104之间，元素和目标值范围在-10^9到10^9之间。
为什么可以假设每个输入都有唯一解？
题目假设每个输入都有唯一解，因此不需要考虑多个解的情况。
如何实现O(n)的算法？
使用哈希表存储已遍历的元素，遍历数组时检查目标值减去当前元素是否在哈希表中。
如果输入数组是[3,3]，目标值是6，输出会是什么？
[0,1]，因为nums[0] + nums[1] == 6。
➡️
