DEV Community
·
LeetCode上的两数之和问题
💡
原文英文，约500词，阅读约需2分钟。
📝
内容提要
给定一个整数数组和目标值，返回两个数的索引，使它们的和等于目标值。可以使用暴力法、两次哈希表或一次哈希表的方法解决，其中一次哈希表方法最优，时间复杂度为O(n)，空间复杂度为O(n)。
🎯
关键要点
- 问题描述：给定一个整数数组和目标值，返回两个数的索引，使它们的和等于目标值。
- 示例1：输入：[2,7,11,15]，目标值：9，输出：[0,1]。
- 示例2：输入：[3,2,4]，目标值：6，输出：[1,2]。
- 示例3：输入：[3,3]，目标值：6，输出：[0,1]。
- 解决方案1：暴力法，通过嵌套循环检查每对元素的和。
- 解决方案2：两次哈希表，第一次遍历存储元素及其索引，第二次检查补数是否存在。
- 解决方案3：一次哈希表，结合插入和查找，时间复杂度为O(n)，空间复杂度为O(n)。
- 优点：时间复杂度最优，实现简洁。
- 缺点：无，达到该问题的最佳时间和空间复杂度。
❓
延伸问答
两数之和问题的基本描述是什么？
给定一个整数数组和目标值，返回两个数的索引，使它们的和等于目标值。
如何使用暴力法解决两数之和问题？
暴力法通过嵌套循环检查每对元素的和是否等于目标值。
一次哈希表方法的时间复杂度和空间复杂度是多少？
时间复杂度为O(n)，空间复杂度为O(n)。
给出一个示例，说明如何找到数组[2,7,11,15]中和为9的两个数的索引。
输入为[2,7,11,15]，目标值为9，输出索引为[0,1]。
两次哈希表方法与一次哈希表方法有什么区别？
两次哈希表方法需要两次遍历数组，而一次哈希表方法只需一次遍历，效率更高。
两数之和问题的最优解法有哪些优点？
最优解法在时间复杂度上最优，且实现简洁，没有缺点。
➡️
