关于LeetCode第一题“两数之和”的一些随笔记录
发布于2021-03-10 18:16 阅读(904) 评论(0) 点赞(9) 收藏(3)
一、题目
如果你刷过LeetCode，你一定知道第一题，“两数之和”。因为我们刷题一般都是从第一题开始的，他也是被LeetCode网站定义为难度为简单的一道题，让我们先来看看他的题目描述：
给定一个整数数组
nums和一个整数目标值target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
提示：
2 <= nums.length <= 103-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
二、暴力枚举法
我们首先会想到的方法自然是暴力枚举法，毕竟这是一个既好理解又好写的方法，甚至它还很节省内存。
对于数组里的每一个元素x，在数组中寻找target-x。
时间复杂度O(N2)，空间复杂度O(1)。
空间复杂度很优秀。可惜，空间就像我的感情一样，是最不值钱的东西。而它浪费了最宝贵的资源——时间。
三、在此思路上改进一下？
在这个基础上，改进一下？
“emm……在数组中查找……”
有了，使用二分查找法更快！
首先使用快排，对数组排序，对于数组里每一个元素x，在数组中二分查找target-x。（禁止中二）
时间复杂度O(nlogn)，已经大大进化了，至于空间复杂度，Who cares！
其实，这个方法还可以继续优化。但是既然使用到了排序，时间复杂度就无法突破O(nlogn)，继续优化只不过是细枝末节，并没有质的突破。
四、哈希Map，真香
其实我们不难注意到题目中这样两句理想化的描述：
- 你可以，假设每种输入只会对应一个答案。
- 只会存在一个有效答案
如果你使用java语言并且了解过HashMap（其他语言也有类似实现，比如C++叫做std::hash_map、python叫做字典），你一定会感叹：“这题目简直就是为了HashMap出的！”
这里引用LeetCode网站给出的Java语言的参考答案。
1 class Solution { 2 public int[] twoSum(int[] nums, int target) { 3 Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>(); 4 for (int i = 0; i < nums.length; ++i) { 5 if (hashtable.containsKey(target - nums[i])) { 6 return new int[]{hashtable.get(target - nums[i]), i}; 7 } 8 hashtable.put(nums[i], i); 9 } 10 return new int[0]; 11 } 12 }
创建HashMap，使用数组中的元素作为key，对应的索引作为value。对于数组里的每一个元素x，首先寻找HashMap中是否存在key为target-x的节点，如果有则返回，如果没有则把x加入到HashMap中。
由于HashMap的出色设计，使这种解题方法的时间复杂度达到了令人惊艳的O(N)。妙啊，真是太妙了。
五、还可以继续优化追求极限性能吗
使用HashMap解决这道问题表现出的性能优势已经足够令人惊艳。那，真的还可以继续优化吗？这就需要我们了解HashMap的底层原理了，欲知详情请看下集……（还可以再水一篇）
原文链接:https://www.cnblogs.com/ohayo/p/14503264.html
所属网站分类: 技术文章 > 博客
作者：木得事
链接：http://www.javaheidong.com/blog/article/112181/b4b327590718e3aedf98/
来源：java黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力