Java算法OJ（10）哈希表练习

1.前言

2.正文

2.1俩数之和

2.2无重复字符的最长子串

2.3罗马数字转整数

2.4整数转罗马数字

3.小结

1.前言

哈喽大家好吖，今天来分享几道哈希表相关的练习题，操作比较基础但是思想比较重要，另外有许多思路与解法都是学习参照题解中诸位大佬的做法，都很有思路对我们很有启发性，欢迎大家在评论区多多交流，废话不多说让我们直接开始吧。

2.正文

2.1俩数之和

提交链接：

1. 两数之和 - 力扣（LeetCode）https://leetcode.cn/problems/two-sum/description/?envType=problem-list-v2&envId=hash-table

这道题当然无脑遍历肯定能直接解出来，但既然要锻炼哈希表的熟练程度就用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无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣（LeetCode）https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=problem-list-v2&envId=hash-table

这道题运用了滑动窗口的思想，即有俩个左右指针通过移动，记录答案后找到满足题意的解。

窗口的定义：

滑动窗口是字符串的一个子串，窗口的两端由两个指针（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罗马数字转整数

13. 罗马数字转整数 - 力扣（LeetCode）https://leetcode.cn/problems/roman-to-integer/description/?envType=problem-list-v2&envId=hash-table

思路如下：

首先我们先认真读题，理解罗马数字的一些规则。

罗马数字使用字符表示数值：
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整数转罗马数字

12. 整数转罗马数字 - 力扣（LeetCode）https://leetcode.cn/problems/integer-to-roman/description/?envType=problem-list-v2&envId=hash-table

这道题比较关键的是把这个哈希表建立出来，题目中给的并不够，只罗列出关键的 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();                // 返回最终罗马数字}
}