时间戳

首页 > 技术文章 > ｌｅｅｔｃｏｄｅ（１）——两数之和（简单）

ｌｅｅｔｃｏｄｅ（１）——两数之和（简单）

songForU 2021-03-03 19:14 原文

方法一：暴力枚举

　　看到题目，脑袋里没有任何其他储备，就只会用两次for循环遍历，然后相加判断是否相等。而且没有做其他的处理，比如没有找到符合要求的，返回空数组［］。

　　时间复杂度：ｏ（ｎ＾２）

　　空间复杂度：ｏ（１）

 1 /**
 2  * @param {number[]} nums
 3  * @param {number} target
 4  * @return {number[]}
 5  */
 6 var twoSum = function(nums, target) {
 7     for(var i=0;i<nums.length;i++){
 8         for(var j = i+1;j<nums.length;j++){
 9             if(nums[i]+nums[j]==target){
10                return [i,j];
11             }
12         }
13     }
14 };

方法二：数据结构之哈希表（Ｍａｐ数据结构）

　　一、相关知识　　

　　哈希表的定义：哈希表是一种根据关键码去寻找值的数据映射结构，也就是说，它通过把关键码值映射到表中一个位置来访问记录，而哈希表的查找时间复杂度为O(1)，可加快查找的速度。

　　而ｊｓ的对象又是基于哈希结构的，本质上是键值对的集合。但是传统上只能用字符串当作键值，因此使他的使用带来了很大的限制，没有java中的hash　map那么强大。

　　于是为了解决这个问题，ＥＳ６提供了Ｍａｐ数据结构。类似于对象，也是键值对的集合，但“键”的范围不限于字符串，各种类型的值（包括对象）都可以当作键值。

　　二、解题思路

　　（１）建立一个ｍａｐ对象，（将数组中的数和下标分别当作ｋｅｙ和ｖａｌｕｅ存起来）。

　　（２）再用一个循环，用target和当前遍历值相减，得到差值。

　　（３）在ｍａｐ中使用ｈａｓ方法，判断此差值是否存在于当前的ｍａｐ对象中，若存在，则返回数值在数组中的下标；不存在则将数组中的数和下标分别当作ｋｅｙ和ｖａｌｕｅ存起来。

　　时间复杂度：ｏ（ｎ）

　　空间复杂度：ｏ（ｎ）【以空间换时间】

 1 /**
 2  * @param {number[]} nums
 3  * @param {number} target
 4  * @return {number[]}
 5  */
 6 var twoSum = function(nums, target) {
 7      let mapO = new Map();//创建map对象
 8     　for(let j=0;j<nums.length;j++){
 9         let num = target-nums[j];
10 
11         if(mapO.has(num)){
12             return [mapO.get(num),j]
13         }else{
14              mapO.set(nums[j],j);
15         } 
16     }
17 };

 

总结：

　　脑袋里没有正儿八经的知识，虽然可以暴力解决处理，思维不够灵活。

　　用ｍａｐ也没有好的思路，而且考虑不够全面。

　　又出了乌龙事件，一直报错，找不到原因，后来发现是圆角和半角的导致的。

 

推荐阅读