从LeetCode实战看C++ STL：用unordered_set优化你的算法（附高频题解析）

从LeetCode实战看C STL用unordered_set优化你的算法附高频题解析在算法竞赛和日常刷题中选择合适的容器往往能决定代码的运行效率。C标准模板库STL提供了丰富的容器选择其中unordered_set因其高效的查找性能成为解决特定问题的利器。本文将结合LeetCode高频题目深入探讨如何利用unordered_set优化算法性能。1. 理解unordered_set的核心优势unordered_set基于哈希表实现平均时间复杂度为O(1)这使其在需要频繁查找的场景中表现优异。与基于红黑树的set相比它放弃了元素的有序性换取了更高的查找效率。1.1 底层实现原理哈希表通过哈希函数将元素映射到不同的桶(bucket)中。理想情况下每个元素都能被均匀分布实现O(1)的查找。但在实际应用中哈希冲突不可避免这会影响性能。// 哈希表示例 unordered_setint nums {1, 2, 3, 4}; cout nums.bucket_count(); // 输出桶的数量1.2 性能对比操作set (红黑树)unordered_set (哈希表)插入O(log n)平均O(1)最差O(n)查找O(log n)平均O(1)最差O(n)删除O(log n)平均O(1)最差O(n)空间复杂度O(n)通常高于set提示当数据量较小时两者性能差异不明显但随着数据量增大unordered_set的优势会逐渐显现。2. LeetCode高频题实战解析2.1 两数之和Two Sum虽然经典的两数之和通常使用unordered_map解决但使用unordered_set的变种同样值得探讨。vectorint twoSum(vectorint nums, int target) { unordered_setint seen; for (int i 0; i nums.size(); i) { int complement target - nums[i]; if (seen.count(complement)) { return {complement, nums[i]}; } seen.insert(nums[i]); } return {}; }这种解法时间复杂度为O(n)空间复杂度也是O(n)比暴力解法的O(n²)高效得多。2.2 存在重复元素Contains Duplicate这是unordered_set的典型应用场景bool containsDuplicate(vectorint nums) { unordered_setint unique_nums; for (int num : nums) { if (unique_nums.count(num)) { return true; } unique_nums.insert(num); } return false; }2.3 最长连续序列Longest Consecutive Sequence这道Hard题目可以巧妙利用unordered_set实现O(n)时间复杂度int longestConsecutive(vectorint nums) { unordered_setint num_set(nums.begin(), nums.end()); int longest 0; for (int num : num_set) { if (!num_set.count(num - 1)) { // 确保从序列起点开始 int current_num num; int current_streak 1; while (num_set.count(current_num 1)) { current_num; current_streak; } longest max(longest, current_streak); } } return longest; }3. 高级用法与注意事项3.1 自定义哈希函数当存储自定义类型时需要提供哈希函数struct Point { int x, y; bool operator(const Point other) const { return x other.x y other.y; } }; struct PointHash { size_t operator()(const Point p) const { return hashint()(p.x) ^ (hashint()(p.y) 1); } }; unordered_setPoint, PointHash point_set;3.2 负载因子与性能优化哈希表的性能受负载因子(load factor)影响unordered_setint nums; nums.max_load_factor(0.7); // 设置最大负载因子 nums.rehash(100); // 预分配空间3.3 C17新特性C17引入了extract和merge操作可以高效地在容器间转移元素unordered_setint set1 {1, 2, 3}; unordered_setint set2 {4, 5, 6}; // 转移单个元素 auto handle set1.extract(1); set2.insert(std::move(handle)); // 合并整个容器 set1.merge(set2);4. 常见陷阱与最佳实践4.1 迭代器失效问题unordered_set的插入操作可能导致迭代器失效unordered_setint nums {1, 2, 3}; auto it nums.begin(); nums.insert(4); // 可能导致it失效 // 此时使用it是未定义行为4.2 哈希冲突与性能下降当哈希函数设计不佳或数据分布特殊时性能可能退化为O(n)。可以通过以下方式优化提供良好的哈希函数调整桶的数量监控负载因子4.3 何时选择set而非unordered_set虽然本文聚焦unordered_set但在以下情况set可能更合适需要有序遍历元素元素比较操作比哈希计算更高效内存限制严格unordered_set通常占用更多内存在实际项目中我经常根据具体场景在两者间切换。对于LeetCode等算法题当题目不要求顺序且需要高效查找时unordered_set通常是首选。