2018-06-06Hashmap

先看一道题:
给定一个数组 nums = [2, 7, 11, 15]
要求找出数组中任意两个数相加等于 target = 9
返回两个数的下标
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

暴力破解方法采用两重循环:

var twoSum = function(nums, target) {
   for(let x=0;x<nums.length;x++){
       for(let y=x+1;y<nums.length;y++){
           if(nums[x]+nums[y]===target){
               return [x,y]
           }
       }
   }
};
twoSum([2,7,11,15],9)

虽然两层循环求出了结果,但是这个解决方法的时间复杂度为N的2次方。
要降低时间复杂度可以采用hashmap,hashmap是一种以键值对存储数据的数据结构,但是它的键是通过散列函数生成的位置或索引,也正因为此,我们可以更快地访问某个值(散列表的查找复杂度为O(1),而其他顺序数据结构如栈、队列、链表的查找复杂度都为O(n),因为需要遍历。
JavaScript的Object本身就是hashmap,JavaScript 的对象属性查找是哈希查找,时间复杂的是 O(1)

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 今天老师给我们发了,紫藤花下这本校刊。 翻开第一页,就是金校长的感言:“爱是最美的底色。”读了这句话我感到老师...
    81a4db820228阅读 239评论 0 0
  • 今天回家啦,一驶入上海,一个个建筑物色彩斑斓、花灯流彩、光鲜亮丽! 南浦大桥更是彩灯闪耀,气势恢宏……还是感觉很亲...
    宝晶阅读 310评论 0 0
  • 人与人之间相处了一段时间之后,经过彼此的认识和了解,就容易产生情。此时的情,是一种情感,一种对对方的表现有强烈的期...
    在水一方zdf阅读 532评论 0 1
  • 下雨了 玻璃窗上的水珠子有我们过去的日子 天很蓝水很清 大黄狗和我们一起游荡在河堤 上午我们在穿衣镜前给自己编细细...
    纸鸟姐姐阅读 315评论 8 7