阅读:2172回复:0
简单算法——哈希
哈希
哈希(Hash)也称为散列,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,这个输出值就是散列值。 哈希表 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。 使用Hash的查询算法分为两步: ① 用Hash函数将被查找的键转化为数组的一个索引。 理想情况下,不同的键都能转化为不同的索引值。当然,这只是理想情况,所以我们需要面对两个或者多个键都会散列到相同的索引值的情况。 ② 处理碰撞冲突的过程 hash算法有很多,这里不再列举。下面是一个简单的例子,使用的就是哈希 题目: 做加法。 给定N个整数,找出有多少对的和为100. 输入示例: ['5','1 99 98 2 2'] 限制内存:100M, 限制时间:1000ms let inputArray = ['5','1 99 98 2 2'] //测试输入 console.log(add(inputArray)) function add(inputArray){ inputArray = inputArray[1].split(" ").map(Number) let hashMap = new Map() let count = 0 inputArray.forEach(item => { if (hashMap.get(100 - item)) { count += hashMap.get(100 - item) } let val = hashMap.get(item) ? hashMap.get(item) + 1 : 1; hashMap.set(item,val) }) return count } 注:有多种方法,比如二分查找也可以求解。 不过新手容易暴力求解(直接双重for循环),妥妥的超时 |
|
最新喜欢:double... |