Leedcode算法专题训练（哈希表）
2024-10-21 09:38:52
Java 中的 HashSet 用于存储一个集合，可以查找元素是否在集合中。如果元素有穷，并且范围不大，那么可以用一个布尔数组来存储一个元素是否存在。例如对于只有小写字符的元素，就可以用一个长度为 26 的布尔数组来存储一个字符集合，使得空间复杂度降低为 O(1)。
Java 中的 HashMap 主要用于映射关系，从而把两个元素联系起来。HashMap 也可以用来对元素进行计数统计，此时键为元素，值为计数。和 HashSet 类似，如果元素有穷并且范围不大，可以用整型数组来进行统计。在对一个内容进行压缩或者其它转换时，利用 HashMap 可以把原始内容和转换后的内容联系起来。
1. 数组中两个数的和为给定值
1. Two Sum (Easy)
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer>map=new HashMap<>();
int[] result=new int[2];
for(int i=0;i<nums.length;i++){
if(map.containsKey(target-nums[i])){
result[0]=map.get(target-nums[i]);
result[1]=i;
break;
}
map.put(nums[i],i);
}
return result;
}
}2. 判断数组是否含有重复元素
217. Contains Duplicate (Easy)
class Solution {
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> set=new HashSet<>();
for(int num:nums){
if(set.contains(num))return true;
else set.add(num);
}
return false;
}
}3. 最长和谐序列
594. Longest Harmonious Subsequence (Easy)
class Solution {
public int findLHS(int[] nums) {
HashMap<Integer,Integer>map=new HashMap<>();
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
int result=0;
for(int num: map.keySet()){
if(map.containsKey(num+1)){
result=Math.max(result,map.get(num+1)+map.get(num));
}
}
return result;
}
}4. 最长连续序列
128. Longest Consecutive Sequence (Hard)
class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer>set=new HashSet<>();
for(int num:nums){
set.add(num);
}
int result=0;
for(int i=0;i<nums.length;i++){
if(!set.contains(nums[i]-1)){
int length=1;
int num=nums[i];
while(set.contains(num+1)){
length+=1;
num+=1;
}
result=Math.max(length,result);
}
}
return result;
}
}最新文章
- js或css文件后面的参数是什么意思？
- Linux C--信号 sigaction函数
- Android studio快捷键大全 和 eclipse对照（原）
- 【Pig源码分析】谈谈Pig的数据模型
- HTML动画分类 HTML5动画 SVG库 SVG工具 Canvas动画工具
- mysql中替换行首字符
- 菜鸟互啄:WINFORM如何实现无聚焦框的Button按钮
- lufylegend库 LGraphics
- MySQL innodb_flush_method
- 2015 多校联赛 ——HDU5402（模拟）
- leetcode 153. Find Minimum in Rotated Sorted Array 、154. Find Minimum in Rotated Sorted Array II 、33. Search in Rotated Sorted Array 、81. Search in Rotated Sorted Array II 、704. Binary Search
- Rimworld单人生存记
- [ 9.26 ]CF每日一题系列—— 771B递推问题
- CMMI三个过程域的流程及达到特定目标、共性目标的要求（RD需求管理过程，PI产品集成过程，TS技术解决方案）
- go语言学习--语法糖
- 人工智能-机器学习之Selenium(chrome驱动，火狐驱动)
- [bug]WCF 内存入口检查失败 Memory gates checking failed
- Word发布到cnblogs文章
- redis常用配置参数详解
- P1021 邮票面值设计