当前位置： 首页 > news >正文

【代码随想录】刷题笔记——哈希表篇

news 2025/7/13 9:45:47

目录

242. 有效的字母异位词

349. 两个数组的交集

202. 快乐数

1. 两数之和

454. 四数相加 II

383. 赎金信

15. 三数之和

18. 四数之和

242. 有效的字母异位词

思路

代码

class Solution {public boolean isAnagram(String s, String t) {if (s.length() != t.length()) return false;int[] cnt = new int[26];for (int i = 0;i < s.length();i++) {cnt[s.charAt(i) - 'a']++;}for (int i = 0;i < t.length();i++) {cnt[t.charAt(i) - 'a']--;}for (int i = 0;i < cnt.length;i++) {if (cnt[i] > 0) return false;}return true;}
}

API：

字符串求length：s.length() 

数组求length：cnt.length

取出 i 位置的元素：s.charAt(i)

代码（排序）

class Solution {public boolean isAnagram(String s, String t) {if (s.length() != t.length()) {return false;}char[] str1 = s.toCharArray();char[] str2 = t.toCharArray();Arrays.sort(str1);Arrays.sort(str2);return Arrays.equals(str1, str2);}
}

API：

字符串转字符数组：s.toCharArray()

比较两字符数组：Arrays.equals(str1, str2)

349. 两个数组的交集

思路

先把 nums1 改成 HashSet 形式，对 nums2 筛选出在 nums1 中的元素，并考虑对 nums2 中的元素去重，放入一个新的 HashSet 中，最后转为答案要求的形式。

代码（数组表示哈希表，有->1 ，无->0）

class Solution {public int[] intersection(int[] nums1, int[] nums2) {int[] temp = new int[1000];int index = 0;//存在不存在的问题int[] map = new int[1001];for (int i = 0;i < nums1.length;i++) {map[nums1[i]] = 1;}for (int i = 0;i < nums2.length;i++) {if (map[nums2[i]] == 1) {temp[index] = nums2[i];map[nums2[i]] = 0;index++;}}int[] result = Arrays.copyOfRange(temp,0,index);return result;}
}

代码（Set集合去重）

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> set1 = new HashSet<>();for (int num : nums1) {set1.add(num);}Set<Integer> set2 = new HashSet<>();for (int num : nums2) {if (set1.contains(num)) {set2.add(num);}}int[] result = new int[set2.size()];int index = 0;for (int num : set2) {result[index++] = num;}return result;}
}

Collection集合的遍历方式

//1.使用增强for遍历集合
for(String s: c){System.out.println(s); 
}
//2. 使用lambda表达式,结合forEach方法
c.forEach(s->System.out.println(s));

202. 快乐数

思路

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

判断sum是否重复出现就可以使用set集合。

还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。

代码

class Solution {public boolean isHappy(int n) {Set<Integer> set = new HashSet<>();while(true) {int temp = getSum(n);if (temp == 1) return true;if (!set.contains(temp)) {set.add(temp);n = temp;}else {return false;}}}//计算每个位置上的数字的平方和private int getSum(int n) {int sum = 0;while (n > 0) {sum += (n%10) * (n%10);n /= 10;}return sum;}
}

新增的方法不能写到默认的public方法里

代码（官方）

class Solution {public boolean isHappy(int n) {Set<Integer> record = new HashSet<>();while (n != 1 && !record.contains(n)) {record.add(n);n = getNextNumber(n);}return n == 1;}private int getNextNumber(int n) {int res = 0;while (n > 0) {int temp = n % 10;res += temp * temp;n = n / 10;}return res;}
}

1. 两数之和

思路

代码

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();int[] result = new int[2];for (int i = 0;i < nums.length;i++) {int key = target - nums[i];if (map.containsKey(key)) {result[0] = i;result[1] = map.get(key);break;}map.put(nums[i],i);}return result;}
}

代码（官方）

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();for (int i = 0; i < nums.length; ++i) {if (hashtable.containsKey(target - nums[i])) {return new int[]{hashtable.get(target - nums[i]), i};}hashtable.put(nums[i], i);}return new int[0];}
}

454. 四数相加 II

思路

代码

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int cnt = 0;Map<Integer,Integer> map = new HashMap<>();//1. 把nums1 nums2相加的所有可能值存到hashmapfor (int i = 0;i < nums1.length;i++) {for (int j = 0;j < nums2.length;j++) {int temp = nums1[i] + nums2[j];if (map.containsKey(temp)) {int a = map.get(temp);map.remove(temp);map.put(temp,a + 1);}else {map.put(temp,1);}}}//2. 遍历nums3 和 nums4，对相加的所有结果判断hashmap中是否存在for (int i = 0;i < nums3.length;i++) {for (int j = 0;j < nums4.length;j++) {int temp2 = 0 - nums3[i] - nums4[j];if (map.containsKey(temp2)) {cnt += map.get(temp2);}}}return cnt;}
}

代码（官方）

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res = 0;Map<Integer, Integer> map = new HashMap<Integer, Integer>();//统计两个数组中的元素之和，同时统计出现的次数，放入mapfor (int i : nums1) {for (int j : nums2) {int sum = i + j;map.put(sum, map.getOrDefault(sum, 0) + 1);}}//统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数for (int i : nums3) {for (int j : nums4) {res += map.getOrDefault(0 - i - j, 0);}}return res;}
}

Map集合API补充

// 遍历键
for (String key : map.keySet()) {System.out.println(key);
}// 遍历值
for (Integer value : map.values()) {System.out.println(value);
}// 获取默认值（若键不存在）
Integer defaultValue = map.getOrDefault("apple", 0); // 返回 0// 合并操作（Java 8+）
map.merge("apple", 5, Integer::sum); // 若键不存在则添加，存在则合并值

Java 8+ 新增默认方法

方法签名说明
V getOrDefault(Object key, V defaultValue)安全获取值（键不存在时返回默认值）
V putIfAbsent(K key, V value)键不存在时才插入
boolean remove(Object key, Object value)仅当键值都匹配时才移除
boolean replace(K key, V oldValue, V newValue)键值都匹配时才替换为新值
V replace(K key, V value)键存在时替换值
void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)批量替换所有值
void forEach(BiConsumer<? super K, ? super V> action)遍历所有键值对
V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)动态计算新值（可删除或更新）
V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)键不存在时计算新值并插入
V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)键存在时计算新值
V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)合并新旧值（常用于计数）

383. 赎金信

代码

class Solution {public boolean canConstruct(String ransomNote, String magazine) {Map<Character,Integer> map = new HashMap<>();for (char s: ransomNote.toCharArray()) {map.merge(s,1,Integer::sum);}for (char m: magazine.toCharArray()) {if (map.containsKey(m)) {map.merge(m,1,(oldValue,newValue) -> oldValue - newValue);}}for (Integer v: map.values()) {if (v > 0) {return false;}}return true;}
}

map.merge(s,1,Integer::sum);       //相当于旧值 + 1

map.merge(m,1,(oldValue,newValue) -> oldValue - newValue);  // //相当于旧值 - 1

代码（官方）

class Solution {public boolean canConstruct(String ransomNote, String magazine) {// shortcutif (ransomNote.length() > magazine.length()) {return false;}// 定义一个哈希映射数组int[] record = new int[26];// 遍历for(char c : magazine.toCharArray()){record[c - 'a'] += 1;}for(char c : ransomNote.toCharArray()){record[c - 'a'] -= 1;}// 如果数组中存在负数，说明ransomNote字符串中存在magazine中没有的字符for(int i : record){if(i < 0){return false;}}return true;}
}

15. 三数之和

思路

代码（官方）

class Solution {//定义三个指针，保证遍历数组中的每一个结果//画图，解答public List<List<Integer>> threeSum(int[] nums) {//定义一个结果集List<List<Integer>> res = new ArrayList<>();//数组的长度int len = nums.length;//当前数组的长度为空，或者长度小于3时，直接退出if(nums == null || len <3){return res;}//将数组进行排序Arrays.sort(nums);//遍历数组中的每一个元素for(int i = 0; i<len;i++){//如果遍历的起始元素大于0，就直接退出//原因，此时数组为有序的数组，最小的数都大于0了，三数之和肯定大于0if(nums[i]>0){break;}//去重，当起始的值等于前一个元素，那么得到的结果将会和前一次相同if(i > 0 && nums[i] == nums[i-1]) continue;int l = i +1;int r = len-1;//当 l 不等于 r时就继续遍历while(l<r){//将三数进行相加int sum = nums[i] + nums[l] + nums[r];//如果等于0，将结果对应的索引位置的值加入结果集中if(sum==0){// 将三数的结果集加入到结果集中res.add(Arrays.asList(nums[i], nums[l], nums[r]));//在将左指针和右指针移动的时候，先对左右指针的值，进行判断//如果重复，直接跳过。//去重，因为 i 不变，当此时 l取的数的值与前一个数相同，所以不用在计算，直接跳while(l < r && nums[l] == nums[l+1]) {l++;}//去重，因为 i不变，当此时 r 取的数的值与前一个相同，所以不用在计算while(l< r && nums[r] == nums[r-1]){r--;} //将 左指针右移，将右指针左移。l++;r--;//如果结果小于0，将左指针右移}else if(sum < 0){l++;//如果结果大于0，将右指针左移}else if(sum > 0){r--;}}}return res;}
}

Arrays.asList() 和 List.of() 

// 使用 List.of()（推荐）
List<Integer> immutableList = List.of(1, 2, 3); // 不可变// 使用 Arrays.asList()
List<Integer> fixedSizeList = Arrays.asList(1, 2, 3); // 大小固定但元素可变// 若需要可变列表，建议显式转换
List<Integer> mutableList = new ArrayList<>(Arrays.asList(1, 2, 3));
mutableList.add(4); // 允许添加元素
场景推荐方法
创建不可变列表List.of()
需要存储 nullArrays.asList()
需修改元素（不增减大小）Arrays.asList()
Java 8 及以下版本Arrays.asList()

18. 四数之和

代码（官方）

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();if (nums == null || nums.length < 4) {return quadruplets;}Arrays.sort(nums);int length = nums.length;for (int i = 0; i < length - 3; i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {break;}if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {continue;}for (int j = i + 1; j < length - 2; j++) {if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {break;}if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {continue;}int left = j + 1, right = length - 1;while (left < right) {long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];if (sum == target) {quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));while (left < right && nums[left] == nums[left + 1]) {left++;}left++;while (left < right && nums[right] == nums[right - 1]) {right--;}right--;} else if (sum < target) {left++;} else {right--;}}}}return quadruplets;}
}

http://www.xdnf.cn/news/1109359.html

相关文章：

  • MySQL 中图标字符存储问题探究：使用外挂法，毕业论文——仙盟创梦IDE
  • shiro550反序列化漏洞复现（附带docker源）
  • 【Docker基础】Dockerfile指令速览：基础常用指令详解
  • Leetcode百题斩-二分搜索
  • 使用langgraph 构建RAG 智能问答代理
  • springboot AOP面向切面编程
  • 连接池深度解析：原理、实现与最佳实践
  • Hap包引用的Hsp报签名错误怎么解决
  • 使用ESM3蛋白质语言模型进行快速大规模结构预测
  • 每日一SQL 【销售分析 III】
  • Python问题记录`No module named ‘matplotlib‘` 问题解决方案
  • 基于SEP3203微处理器的嵌入式最小硬件系统设计
  • 基于 Python 的数据分析技术综述
  • 剑指offer56_数组中唯一只出现一次的数字
  • 【MogDB】一种基于ctid分片并发查询以提升大表查询性能的方式
  • 【go】gopath、GO111MODULE=on作用
  • Javaweb- 11 MVC架构模式
  • JDK官方文档下载教程
  • 计算机视觉 之 经典模型汇总
  • 快速排序递归和非递归方法的简单介绍
  • 牛客：HJ19 简单错误记录[华为机考][字符串]
  • phpstudy搭建pikachu靶场
  • CCS-MSPM0G3507-2-定时器中断
  • SpringAI实现保存聊天记录到redis中
  • C++单元测试gtest技术
  • RHCSA（2）
  • 云端docker小知识
  • sqli-labs靶场通关笔记：第7-8关 布尔盲注
  • 一文理解锂电池充电、过放修复与电量测量：从原理到实战
  • Ubuntu安装Jenkins