LeetCode Hot 100（哈希篇）
1. 两数之和
很多涉及两个变量的题目，都可以枚举其中一个变量，把它当成常量看待，从而转换成一个变量的问题。代码实现时，通常来说枚举右，维护左是更加好写的
时间复杂度：O ( n ) O(n)O(n)
空间复杂度：O ( n ) O(n)O(n)
Java 代码：
classSolution{publicint[]twoSum(int[]nums,inttarget){Map<Integer,Integer>cnt=newHashMap<>();for(inti=0;i<nums.length;i++){if(cnt.containsKey(target-nums[i])){returnnewint[]{cnt.get(target-nums[i]),i};}cnt.put(nums[i],i);}returnnewint[]{-1,-1};}}Python 代码：
classSolution:deftwoSum(self,nums:List[int],target:int)->List[int]:dic={}foriinrange(0,len(nums)):x=target-nums[i]ifxindic:return[i,dic[x]]dic[nums[i]]=ireturn[-1,-1]49. 字母异位词分组
如果两个字符串是字母异位词，那经过排序之后，两个字符串是一样的。把经排序后的字符串作为哈希表的 key，这个可以映射到这个 key 的就是同一组的。
时间复杂度：O ( n m l o g m ) O(nmlogm)O(nmlogm)
空间复杂度：O ( n ) O(n)O(n)
Java 代码：
classSolution{publicList<List<String>>groupAnagrams(String[]strs){Map<String,List<String>>cnt=newHashMap<>();for(Stringstr:strs){char[]charStr=str.toCharArray();Arrays.sort(charStr);StringsortStr=newString(charStr);if(cnt.containsKey(sortStr)){cnt.get(sortStr).add(str);}else{cnt.put(sortStr,newArrayList<>(Arrays.asList(str)));}}List<List<String>>ans=newArrayList<>();for(Stringkey:cnt.keySet()){ans.add(cnt.get(key));}returnans;}}Python 代码：
classSolution:defgroupAnagrams(self,strs:List[str])->List[List[str]]:dic={}forsinstrs:sortedStr="".join(sorted(s))ifsortedStrindic:dic[sortedStr].append(s)else:dic[sortedStr]=[s]ans=[]forkindic.keys():ans.append(dic[k])returnans128. 最长连续序列
对于数组中的每一个序列都从该序列的最开始记录长度。利用哈希表，首先将数组中的元素全部存储到哈希表中，对于数组中的一个数 x 如果哈希表中记录有 x-1，则说明 x 不是一个连续序列的开始，直接跳过，直到找到一个序列的首位，开始递增的查询连续序列是否存在，查询结束时也就知道了以 x 开始的最长连续序列的长度，最后再记录 x 已经被记录过最长连续序列，避免重复计算。
时间复杂度：O ( n ) O(n)O(n)
空间复杂度：O ( n ) O(n)O(n)
Java代码：
classSolution{publicintlongestConsecutive(int[]nums){Set<Integer>set=newHashSet<>();for(intnum:nums){set.add(num);}intans=0;for(inti=0;i<nums.length;i++){if(set.contains(nums[i]-1)){continue;}inttmp=nums[i];while(set.contains(tmp)){set.remove(tmp);tmp++;}ans=Math.max(ans,tmp-nums[i]);}returnans;}}Python 代码：
classSolution:deflongestConsecutive(self,nums:List[int])->int:s=set(nums)ans=0forxins:if(x-1)ins:continuet=xwhiletins:t+=1ans=max(ans,t-x)returnans