程序员最近都爱上了这个网站  程序员们快来瞅瞅吧!  it98k网:it98k.com

本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

关于LeetCode第一题“两数之和”的一些随笔记录

发布于2021-03-10 18:16     阅读(764)     评论(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黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

9 0
收藏该文
已收藏

评论内容:(最多支持255个字符)