LeetCode Hot 100（哈希篇）

1. 两数之和很多涉及两个变量的题目都可以枚举其中一个变量把它当成常量看待从而转换成一个变量的问题。代码实现时通常来说枚举右维护左是更加好写的时间复杂度O ( n ) O(n)O(n)空间复杂度O ( n ) O(n)O(n)Java 代码classSolution{publicint[]twoSum(int[]nums,inttarget){MapInteger,IntegercntnewHashMap();for(inti0;inums.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)):xtarget-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{publicListListStringgroupAnagrams(String[]strs){MapString,ListStringcntnewHashMap();for(Stringstr:strs){char[]charStrstr.toCharArray();Arrays.sort(charStr);StringsortStrnewString(charStr);if(cnt.containsKey(sortStr)){cnt.get(sortStr).add(str);}else{cnt.put(sortStr,newArrayList(Arrays.asList(str)));}}ListListStringansnewArrayList();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){SetIntegersetnewHashSet();for(intnum:nums){set.add(num);}intans0;for(inti0;inums.length;i){if(set.contains(nums[i]-1)){continue;}inttmpnums[i];while(set.contains(tmp)){set.remove(tmp);tmp;}ansMath.max(ans,tmp-nums[i]);}returnans;}}Python 代码classSolution:deflongestConsecutive(self,nums:List[int])-int:sset(nums)ans0forxins:if(x-1)ins:continuetxwhiletins:t1ansmax(ans,t-x)returnans