leetCode-热题100-哈希合集（JavaScript)

1-两数之和

题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
题解

var twoSum=function(nums, target){// 使用哈希表解题 const map=new Map();// 遍历数组 for(let i=0;i<nums.length;i++){// 查找map中是否有target - nums[i]的value值，如有，返回其key和当前数组元素的下标 if(map.has(target - nums[i])){return[map.get(target-nums[i]),i]}// 未在map的value中找到另一个数，将当前数组元素值以及数组索引下标加入map中 map.set(nums[i],i)}// 找不到返回空值return[]};

使用Map数据结构来存储每个数字对应的下标
● key是数字的值
● value的该数字在数组中的位置
遍历源数组，当前遍历到的数字为nums[i]，如果Map中存在以 target - nums[i]为key值的元素，说明找到了两个数字加起来等于target的值，这时候返回当前索引和 Map中以 target - nums[i]为key值对应的value值即可。

2-字母异位词分组

题目描述
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
解释：
● 在 strs 中没有字符串可以通过重新排列来形成 “bat”。
● 字符串 “nat” 和 “tan” 是字母异位词，因为它们可以重新排列以形成彼此。
● 字符串 “ate” ，“eat” 和 “tea” 是字母异位词，因为它们可以重新排列以形成彼此。
题解

var groupAnagrams=function(strs){// 使用哈希表解题 const map=new Map()// 遍历字符数组 for(let s of strs){// 使用split()将字符串分割成单个字符 // 使用sort()将字符数组排序，返回字符数组 // 使用join()将排序后的字符数组连接成字符串 // sortS作为哈希表的key值，具有唯一性 const sortedS=s.split('').sort().join('')// 当前map中没有此key值，将key值存入map，value值设为空数组 if(!map.has(sortedS)){map.set(sortedS,[])}// 当前map中有此key值，将当前原始字符串存入map的value数组中 map.get(sortedS).push(s)}// map.values()获取map中的所有value // Array.from()转成数组返回returnArray.from(map.values())};

时间复杂度：O(nmlogm)，其中 n 为 strs 的长度，m 为 strs[i] 的长度。每个字符串排序需要 O(mlogm)的时间，有 n 个字符串，所以总的时间复杂度为 O(nmlogm)。 空间复杂度：O(nm)。
使用哈希表分组，将排序后的str[i]作为哈希表的key，排序前的str[i]最为哈希表的value

3-最长连续序列

题目描述
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
题解

var longestConsecutive=function(nums){// 使用哈希集合解题（只需要存储value），无重复、可快速查询的元素集合 constset=new Set(nums)// 初始化最长连续序列的长度letans=0// 遍历哈希集合 for(let s ofset){// 判断集合的当前元素是否是起点[一个序列的「起点 s」，一定满足「s-1 」不在set中]if(set.has(s-1)){// 当前元素不是最长连续序列的起点，直接跳过continue}// 判断当前元素下一个连续的元素值是否在set中lety=s +1while(set.has(y)){y++}// 更新最长序列的长度 ans=Math.max(ans,y-s)// 优化剪枝：如果当前最长长度的2倍 ≥ 集合总大小，直接终止循环 if(ans *2>set.size){break}}returnans};

使用哈希集合，利用Set()方法将数组转换成哈希集合（无序无重复），之后遍历哈希集合set，不断记录以当前节点为起点的连续序列的长度，最后做剪枝优化