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

Ne0inhk

15 Mar 2026 — 8 min read

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(); // 返回最终罗马数字 } }