美文网首页
2018-06-06Hashmap

2018-06-06Hashmap

作者: NOTEBOOK2 | 来源:发表于2018-06-06 23:18 被阅读0次

先看一道题:
给定一个数组 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)

相关文章

  • 2018-06-06Hashmap

    先看一道题:给定一个数组 nums = [2, 7, 11, 15]要求找出数组中任意两个数相加等于 target...

网友评论

      本文标题:2018-06-06Hashmap

      本文链接:https://www.haomeiwen.com/subject/ycwisftx.html