1. 题目背景与核心挑战
这三道LeetCode题目（12、13、14、15）都是经典的字符串和数字处理问题，在技术面试中出现频率极高。作为C++选手，我们需要特别注意类型转换、边界条件和算法效率的处理。这些题目看似基础，但实际暗藏多个考察点：
- 数字与罗马字转换（12/13题）：考验对特殊规则的抽象能力
- 最长公共前缀（14题）：字符串处理的经典案例
- 三数之和（15题）：双指针算法的典型应用
我在刷题过程中发现，很多解法虽然能通过测试，但在代码整洁度和执行效率上仍有优化空间。下面分享我的解题思路和优化心得。
2. 整数转罗马数字（第12题）
2.1 贪心算法实现
罗马数字有7个基本符号，但实际组合方式存在特殊规则（如IV表示4）。最直观的解法是建立数值与符号的映射表：
cpp复制const vector<pair<int, string>> valueSymbols = {
{1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
{100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
{10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}
};
关键点在于映射表需要按从大到小排序，这样可以用贪心算法逐步减去最大可能值：
cpp复制string intToRoman(int num) {
string res;
for (const auto &[value, symbol] : valueSymbols) {
while (num >= value) {
num -= value;
res += symbol;
}
if (num == 0) break;
}
return res;
}
注意：这里使用C++17的结构化绑定语法，需要编译器支持-std=c++17
2.2 边界情况处理
- 输入范围：题目保证1 ≤ num ≤ 3999，但实际工程中应添加校验
- 零值处理：罗马数字没有零的表示法
- 大数优化：当处理接近3999的数字时，可以预先计算高频组合
3. 罗马数字转整数（第13题）
3.1 逆向处理技巧
与第12题相反，这里需要将罗马字转为整数。关键点在于识别特殊组合（IV、IX等）：
cpp复制unordered_map<char, int> symbolValues = {
{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
{'C', 100}, {'D', 500}, {'M', 1000}
};
int romanToInt(string s) {
int res = 0;
for (int i = 0; i < s.size(); ++i) {
int value = symbolValues[s[i]];
if (i < s.size() - 1 && value < symbolValues[s[i + 1]]) {
res -= value;
} else {
res += value;
}
}
return res;
}
3.2 性能优化对比
测试发现unordered_map比map快约30%，因为：
- 哈希表查询时间复杂度O(1)
- 数据量小（仅7个元素）时哈希冲突少
4. 最长公共前缀（第14题）
4.1 纵向扫描法
最直观的方法是逐个字符比较所有字符串：
cpp复制string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
for (int i = 0; i < strs[0].size(); ++i) {
char c = strs[0][i];
for (int j = 1; j < strs.size(); ++j) {
if (i == strs[j].size() || strs[j][i] != c) {
return strs[0].substr(0, i);
}
}
}
return strs[0];
}
4.2 时间复杂度分析
设n为字符串数量，m为最短字符串长度：
- 最佳情况：O(m)（第一个字符就不匹配）
- 最差情况：O(n*m)
5. 三数之和（第15题）
5.1 排序+双指针解法
这是面试中最常考的中等难度题目，核心在于去重和剪枝：
cpp复制vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
for (int i = 0; i < nums.size() && nums[i] <= 0; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
int left = i + 1, right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
++left;
} else if (sum > 0) {
--right;
} else {
res.push_back({nums[i], nums[left], nums[right]});
// 跳过重复元素
while (left < right && nums[left] == nums[left + 1]) ++left;
while (left < right && nums[right] == nums[right - 1]) --right;
++left;
--right;
}
}
}
return res;
}
5.2 关键优化点
- 提前终止：当nums[i] > 0时直接break
- 去重处理：连续相同值跳过
- 双指针移动：根据sum结果决定移动方向
6. 通用优化技巧
6.1 输入预处理
- 排序往往是优化前提（如第15题）
- 使用reserve预分配空间减少内存操作
- 对于字符串操作，优先考虑string_view（C++17）
6.2 容器选择原则
- 需要快速查找：unordered_map/unordered_set
- 需要有序遍历：map/set
- 纯数组操作：vector（最紧凑的内存布局）
6.3 调试技巧
在LeetCode调试时，可以添加打印语句：
cpp复制#define DEBUG 1
#if DEBUG
#define print(x) cout << #x << ": " << x << endl
#else
#define print(x)
#endif
7. 常见错误排查
- 数组越界：始终检查容器是否为空（如第14题）
- 整数溢出：特别是第13题中res可能超过INT_MAX
- 迭代器失效：在循环中修改容器会导致未定义行为
- 字符大小写：罗马数字必须大写（题目已保证）
- 多解去重：第15题必须正确处理重复解
8. 测试用例设计
建议自行补充这些边界测试：
cpp复制// 第12题
assert(intToRoman(1994) == "MCMXCIV"); // 包含所有特殊组合
// 第13题
assert(romanToInt("LVIII") == 58); // 不含减法规则
assert(romanToInt("MCMXCIV") == 1994); // 含全部减法规则
// 第14题
assert(longestCommonPrefix({"flower","flow","flight"}) == "fl");
assert(longestCommonPrefix({"dog","racecar","car"}) == "");
// 第15题
vector<vector<int>> expected = {{-1,-1,2}, {-1,0,1}};
assert(threeSum({-1,0,1,2,-1,-4}) == expected);
9. 进阶挑战
尝试用这些方法解决相似题目：
- 第16题：最接近的三数之和（稍改第15题代码）
- 第17题：电话号码的字母组合（回溯法）
- 第18题：四数之和（扩展第15题思路）
在实际面试中，面试官可能会要求：
- 不排序实现第15题（哈希法，但更难去重）
- 处理更大范围的罗马数字（如扩展符号）
- 找出所有不重复公共前缀（而不仅是最长）