LeetCode 0013 罗马数字转整数（Roman to Integer）：哈希表与相邻字符比较的单遍扫描解法

LeetCode 0013 罗马数字转整数（Roman to Integer）：哈希表与相邻字符比较的单遍扫描解法

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

导读

本文基于仓库 articles/roman-to-integer.md 中的算法讲解，系统梳理 LeetCode 0013「罗马数字转整数」的哈希表解法：从左到右扫描字符串，用"当前字符小于下一字符则减、否则加"这一条统一规则同时处理常规加法与减法记数法（如 IV = 4）。仓库在 python/0013-roman-to-integer.py、cpp/0013-roman-to-integer.cpp、go/0013-roman-to-integer.go 等十余种语言目录下提供了可直接运行的实现。读完本文，你将掌握该题的 O(n) 时间、O(1) 空间解法，理解六种减法记数规则的本质，并能规避两个最常见的边界错误。

一、问题背景：罗马数字的符号表与减法规则

罗马数字由七个符号构成，每个符号对应一个固定的整数值：

| 符号 | 值 | | ---- | -- | | I | 1 | | V | 5 | | X | 10 | | L | 50 | | C | 100 | | D | 500 | | M | 1000 |

例如2写作II（两个 1 相加），12写作XII（X + II），27写作XXVII（XX + V + II）。罗马数字通常从左到右按"从大到小"书写，但存在六种特殊的**减法记数（subtractive notation）**情形——较小的符号放在较大的符号之前表示相减：

• I可放在V（5）和X（10）之前，构成 4 和 9；
• X可放在L（50）和C（100）之前，构成 40 和 90；
• C可放在D（500）和M（1000）之前，构成 400 和 900。

例如MCMXCIV应解析为M = 1000, CM = 900, XC = 90, IV = 4，结果共1994。这正是题目要求处理的核心难点。

二、前置知识（Prerequisites）

在动手实现之前，需要具备以下三个基础能力：

• Hash Map（哈希表）：用于存储每个罗马数字字符对应的整数值，实现 O(1) 查找；
• 字符串遍历（String Iteration）：逐字符扫描字符串，并在遍历过程中比较相邻元素；
• 条件逻辑（Conditional Logic）：根据当前字符值与下一字符值的大小关系，决定当前字符是加还是减。

三、核心思想（Intuition）

罗马数字的常规写法是从左到右累加。解题的关键洞察在于减法记数法的处理：当一个较小的值出现在较大的值之前时（如IV），实际含义是相减而非相加（IV = 4而非I + V = 6）。

于是可以提炼出一条统一规则：从左到右扫描时，如果当前符号的值小于下一个符号的值，就减去当前符号的值；否则加上当前符号的值。这一条规则同时优雅地覆盖了普通加法与减法两种情况，避免了为六种特殊组合单独写分支。

以MCMXCIV为例逐步推演：

最终得到 1994，与题目示例一致。

四、算法步骤（Algorithm）

1. 创建哈希表，为每个罗马数字字符I, V, X, L, C, D, M存储其对应的整数值；
2. 将结果初始化为0；
3. 遍历字符串中的每一个字符：
   • 若当前字符的值小于下一字符的值，则从结果中减去当前字符的值；
   • 否则，将当前字符的值加到结果中；
4. 返回最终结果。

注意第 3 步中"与下一字符比较"的动作在最后一个字符处必须跳过，因为该字符没有后继，只需直接累加即可。

五、多语言实现（完整代码）

以下实现与仓库源码一一对应，可直接在各自语言的 LeetCode 环境中运行。

Python

class Solution: def romanToInt(self, s: str) -> int: roman = { "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000 } res = 0 for i in range(len(s)): if i + 1 < len(s) and roman[s[i]] < roman[s[i + 1]]: res -= roman[s[i]] else: res += roman[s[i]] return res

与 python/0013-roman-to-integer.py 中的实现完全一致：i + 1 < len(s)先做越界检查，再访问s[i + 1]，避免了最后一个字符的索引越界。

Java

public class Solution { public int romanToInt(String s) { Map<Character, Integer> roman = new HashMap<>(); roman.put('I', 1); roman.put('V', 5); roman.put('X', 10); roman.put('L', 50); roman.put('C', 100); roman.put('D', 500); roman.put('M', 1000); int res = 0; for (int i = 0; i < s.length(); i++) { if (i + 1 < s.length() && roman.get(s.charAt(i)) < roman.get(s.charAt(i + 1))) { res -= roman.get(s.charAt(i)); } else { res += roman.get(s.charAt(i)); } } return res; } }

C++

class Solution { public: int romanToInt(string s) { unordered_map<char, int> roman = { {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000} }; int res = 0; for (int i = 0; i < s.size(); i++) { if (i + 1 < s.size() && roman[s[i]] < roman[s[i + 1]]) { res -= roman[s[i]]; } else { res += roman[s[i]]; } } return res; } };

JavaScript

class Solution { /** * @param {string} s * @return {number} */ romanToInt(s) { const roman = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000, }; let res = 0; for (let i = 0; i < s.length; i++) { if (i + 1 < s.length && roman[s[i]] < roman[s[i + 1]]) { res -= roman[s[i]]; } else { res += roman[s[i]]; } } return res; } }

C#

public class Solution { public int RomanToInt(string s) { Dictionary<char, int> roman = new Dictionary<char, int> { {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000} }; int res = 0; for (int i = 0; i < s.Length; i++) { if (i + 1 < s.Length && roman[s[i]] < roman[s[i + 1]]) { res -= roman[s[i]]; } else { res += roman[s[i]]; } } return res; } }

Go

func romanToInt(s string) int { roman := map[byte]int{ 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000, } res := 0 for i := 0; i < len(s); i++ { if i+1 < len(s) && roman[s[i]] < roman[s[i+1]] { res -= roman[s[i]] } else { res += roman[s[i]] } } return res }

仓库中的 go/0013-roman-to-integer.go 即为上述实现，其中map[byte]int以字节为键，直接利用s[i]的byte类型完成查找。

Kotlin

class Solution { fun romanToInt(s: String): Int { val roman = mapOf( 'I' to 1, 'V' to 5, 'X' to 10, 'L' to 50, 'C' to 100, 'D' to 500, 'M' to 1000 ) var res = 0 for (i in s.indices) { if (i + 1 < s.length && roman[s[i]]!! < roman[s[i + 1]]!!) { res -= roman[s[i]]!! } else { res += roman[s[i]]!! } } return res } }

注意 Kotlin 中map[key]返回可空类型，需要用!!断言非空；由于输入保证只含七个合法罗马字符，该断言是安全的。

Swift

class Solution { func romanToInt(_ s: String) -> Int { let roman: [Character: Int] = [ "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000 ] let chars = Array(s) var res = 0 for i in 0..<chars.count { if i + 1 < chars.count && roman[chars[i]]! < roman[chars[i + 1]]! { res -= roman[chars[i]]! } else { res += roman[chars[i]]! } } return res } }

Swift 中先通过Array(s)将字符串转为字符数组，既方便按下标访问，也保证了chars[i]与chars[i + 1]的相邻比较语义正确。

Rust

impl Solution { pub fn roman_to_int(s: String) -> i32 { let roman = |c: u8| -> i32 { match c { b'I' => 1, b'V' => 5, b'X' => 10, b'L' => 50, b'C' => 100, b'D' => 500, b'M' => 1000, _ => 0, } }; let bytes = s.as_bytes(); let mut res = 0; for i in 0..bytes.len() { if i + 1 < bytes.len() && roman(bytes[i]) < roman(bytes[i + 1]) { res -= roman(bytes[i]); } else { res += roman(bytes[i]); } } res } }

Rust 版本将字符到值的映射写成闭包roman，通过s.as_bytes()获得字节切片，配合b'I'字节字面量匹配，实现零堆分配的轻量查找。

六、复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为输入字符串长度。每个字符只被访问常数次（当前字符的查找与最多一次"下一字符"的比较），哈希表查找本身为 O(1)。
• 空间复杂度：$O(1)$，因为哈希表只包含固定的 7 个字符映射，与输入规模无关。

七、常见陷阱（Common Pitfalls）

1. 总是相加而忽略减法记数

最常见的错误是遍历时无条件累加每个罗马字符的值，导致IV被算成I + V = 6而非V - I = 4。修复方法即本文的核心规则：比较当前字符与下一字符的值，当前者较小时做减法。

2. 相邻字符比较时的越界错误（Off-by-One）

在判断"当前字符是否小于下一字符"时，如果忘记验证i + 1是否在字符串长度范围内，会在访问s[i + 1]时触发数组越界。必须始终先检查i + 1 < len(s)再进行访问——这一点在 articles/roman-to-integer.md 中被明确强调，也是上述所有语言实现中if条件的标准写法。

八、仓库源码中的其他实现变体

仓库在 cpp/0013-roman-to-integer.cpp 等文件中提供了与文档思路一致但风格各异的实现，可作为对比学习的素材。

C 语言：显式取出"下一个值"

c/0013-roman-to-integer.c 将字符转值逻辑抽成value(char)辅助函数（switch返回 1~1000，非法字符返回 0）。循环体内先取valueCurrent = value(s[i])，再判断(i + 1) < len：有后继则取valueNext，否则将valueNext置为0——这样末尾字符必然走"累加"分支，从另一角度规避了越界问题。

Java：先加后修正

仓库中的 java/0013-roman-to-integer.java 采用不同的等价写法：不向前看，而是向后看——若当前字符值大于前一字符值，说明前一轮被多加了，用result += map.get(s.charAt(i)) - 2 * map.get(s.charAt(i - 1))完成修正（先去掉之前多加的一次，再补上减法语义）。该变体同样得到正确结果，展示了同一算法"向前比较"与"向后修正"两种视角。

C++：用优先级函数比较相邻字符

cpp/0013-roman-to-integer.cpp 额外维护了一个prec(char)优先级函数（I→1, V→2, …, M→7），当prec(s[i]) < prec(s[i + 1])时执行ans = ans - val(s[i]) + val(s[i + 1])并跳过下一字符（i++），相当于把"相减的一对"一次性合并处理。从源码结构看，这种写法把"比较"与"取值"分离，便于扩展到更多字符集。

Rust：从右向左的函数式写法

rust/0013-roman-to-integer.rs 还提供了一种函数式变体roman_to_int_functional：用s.chars().rfold(0, ...)从右向左折叠，累加器acc已包含右侧子串的和，因此只需判断"当前字符是否小于其右侧已累积的量级"（如I在acc >= 5时取-1），即可在单次折叠中完成全部计算，无需索引与越界判断。

九、验证与测试建议

建议用以下几组用例覆盖常规加法、全部六种减法组合与混合场景：

运行仓库中的对应实现（如python/0013-roman-to-integer.py、go/0013-roman-to-integer.go、typescript/0013-roman-to-integer.ts）即可验证上述用例全部通过。

十、延伸阅读

本解法与仓库中的 articles/integer-to-roman.md（整数转罗马数字）互为逆运算，可对照学习贪心取值的思路；哈希表查值的技巧在 articles/is-anagram.md、articles/two-integer-sum.md 等题目中同样适用。仓库 README.md 汇总了全部题解目录，可按语言（python/、java/、cpp/、go/、rust/等）继续检索。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode