Java算法OJ（10）哈希表练习
目录
1.前言
哈喽大家好吖，今天来分享几道哈希表相关的练习题，操作比较基础但是思想比较重要，另外有许多思路与解法都是学习参照题解中诸位大佬的做法，都很有思路对我们很有启发性，欢迎大家在评论区多多交流，废话不多说让我们直接开始吧。
2.正文
2.1俩数之和
提交链接：
这道题当然无脑遍历肯定能直接解出来，但既然要锻炼哈希表的熟练程度就用HashSet来完成：
先初始化该哈希表。遍历，如果存在一个数组的数，满足目标值减去当下遍历到的这个数，那么存在解。如果遍历到最后都没有返回，那么无解。
class Solution { public int[] twoSum(int[] nums, int target) { Map <Integer,Integer>hashMap = new HashMap<>(); for(int i = 0;i < nums.length;i++){ if(hashMap.containsKey(target - nums[i])){ return new int[]{hashMap.get(target - nums[i]),i}; } hashMap.put(nums[i],i); } return new int[0]; } }时间复杂度：遍历数组只需 O(n)O(n)O(n)。哈希表的插入和查找操作平均时间复杂度是 O(1)O(1)O(1)。总体时间复杂度：O(n)O(n)O(n)。空间复杂度：额外使用了一个哈希表存储数组中的元素和索引，最坏情况下需要存储 nnn 个元素。空间复杂度：O(n)O(n)O(n)。
2.2无重复字符的最长子串
这道题运用了滑动窗口的思想，即有俩个左右指针通过移动，记录答案后找到满足题意的解。
窗口的定义：滑动窗口是字符串的一个子串，窗口的两端由两个指针（i和right）表示。窗口的内容始终保持无重复字符。双指针移动规则：右指针right：用于扩展窗口，表示当前扫描到的位置。左指针i：用于收缩窗口，解决窗口内出现重复字符的问题。用数据结构维护窗口状态：使用一个HashSet（或哈希表）存储窗口内的字符，快速判断窗口中是否已经包含某个字符。过程描述：初始化窗口左右边界（i和right），以及存储结果的变量（ans）。遍历字符串，用右指针逐步扩展窗口；如果窗口内出现重复字符，用左指针逐步缩小窗口，直到窗口重新无重复。在每一步中，更新窗口的长度并维护最长子串的长度。结束条件：当右指针到达字符串末尾时，遍历结束，返回最长子串的长度。
class Solution { public int lengthOfLongestSubstring(String s) { Set<Character> set = new HashSet<Character>(); int right = 0; int ans = 0; for(int i = 0;i < s.length();i++){ if(i != 0){ set.remove(s.charAt(i - 1));//左指针 } while(right < s.length() && !set.contains(s.charAt(right))){ set.add(s.charAt(right)); right++; } ans = Math.max(ans,(right - i)); } return ans; } }时间复杂度：每个字符至多被访问两次（一次被左指针移除，一次被右指针添加）。总时间复杂度为 O(n)O(n)O(n)。空间复杂度：使用了 HashSet 存储字符，空间复杂度为 O(k)O(k)O(k)。2.3罗马数字转整数
思路如下：
首先我们先认真读题，理解罗马数字的一些规则。罗马数字使用字符表示数值：I=1,V=5,X=10,L=50,C=100,D=500,M=1000。大部分情况下，罗马数字字符按照从左到右从大到小排列，并直接相加。如：VII = 5 + 1 + 1 = 7但在特定情况下，较小值的字符出现在较大值字符的左边时，表示减法。如：IV = 5 - 1 = 4，IX = 10 - 1 = 9。
算法设计：利用一个哈希表（HashMap）存储罗马字符和整数值之间的映射关系。遍历字符串，每次提取当前字符的值，并判断是否需要减去还是加上该值。如果当前字符的值小于下一个字符的值（value < next_value），说明需要减去当前值。否则，将当前值加到结果中。
算法实现步骤初始化映射表：将每个罗马字符对应的值存入一个哈希表中，便于快速查找。遍历字符串：当前字符值（value）与下一个字符值（next_value）进行比较：如果value < next_value，结果减去当前值；否则，结果加上当前值。循环直到字符串结束。返回结果：遍历完成后，累积的结果即为整数值。
class Solution { public int romanToInt(String s) { Map<Character, Integer> map = new HashMap<Character, Integer>() {{ put('I', 1); put('V', 5); put('X', 10); put('L', 50); put('C', 100); put('D', 500); put('M', 1000); }}; int ans = 0; int n = s.length(); for(int i = 0;i < s.length();i++){ int value = map.get(s.charAt(i)); if(i < n - 1 && value < map.get(s.charAt(i + 1))){ ans -= value; } else { ans += value; } } return ans; } }时间复杂度：O(n)O(n)O(n)，其中 nnn 是罗马数字字符串的长度，每个字符只访问一次。空间复杂度：O(1)O(1)O(1)，哈希表的大小是固定的，与输入规模无关。
2.4整数转罗马数字
这道题比较关键的是把这个哈希表建立出来，题目中给的并不够，只罗列出关键的 7 种数字字符，加上 6 种特殊数字所对应的罗马数字，就足够了：
建立映射关系：使用两个数组values和symbols分别存储数值与对应的罗马符号，并按照数值从大到小排列。
遍历处理：从高到低依次处理每一个罗马数字的数值和符号。如果当前数值可以被整数num包含，减去该值，并将对应的罗马符号添加到结果字符串中。重复处理当前符号，直到num小于该数值。
提前结束：如果整数num减为 0，则提前退出循环以优化效率。
返回结果：最终拼接完成后返回结果字符串。
class Solution { // 定义数值与罗马数字的对应关系 int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; public String intToRoman(int num) { StringBuilder roman = new StringBuilder(); // 使用 StringBuilder 拼接字符串 for (int i = 0; i < values.length; ++i) { while (num >= values[i]) { num -= values[i]; // 减去当前数值 roman.append(symbols[i]); // 添加对应的罗马符号 } if (num == 0) break; // 如果数字为 0，提前退出循环 } return roman.toString(); // 返回最终罗马数字 } } 时间复杂度：O(1)O(1)O(1)
罗马数字的种类和数量是固定的，因此算法的循环次数是常数，与输入大小无关。空间复杂度：O(1)O(1)O(1)
除了固定大小的数组和结果字符串外，额外的空间使用量与输入无关。
3.小结
今天的分享到这里就结束了，喜欢的小伙伴不要忘记点点赞点个关注，你的鼓励就是对我最大的支持，加油！
