从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_set<int> nums = {1, 2, 3, 4}; cout << nums.bucket_count(); // 输出桶的数量

1.2 性能对比

提示：当数据量较小时，两者性能差异不明显；但随着数据量增大，unordered_set的优势会逐渐显现。

2. LeetCode高频题实战解析

2.1 两数之和（Two Sum）

虽然经典的"两数之和"通常使用unordered_map解决，但使用unordered_set的变种同样值得探讨。

vector<int> twoSum(vector<int>& nums, int target) { unordered_set<int> 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(vector<int>& nums) { unordered_set<int> 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(vector<int>& nums) { unordered_set<int> 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 hash<int>()(p.x) ^ (hash<int>()(p.y) << 1); } }; unordered_set<Point, PointHash> point_set;

3.2 负载因子与性能优化

哈希表的性能受负载因子(load factor)影响：

unordered_set<int> nums; nums.max_load_factor(0.7); // 设置最大负载因子 nums.rehash(100); // 预分配空间

3.3 C++17新特性

C++17引入了extract和merge操作，可以高效地在容器间转移元素：

unordered_set<int> set1 = {1, 2, 3}; unordered_set<int> set2 = {4, 5, 6}; // 转移单个元素 auto handle = set1.extract(1); set2.insert(std::move(handle)); // 合并整个容器 set1.merge(set2);

4. 常见陷阱与最佳实践

4.1 迭代器失效问题

unordered_set的插入操作可能导致迭代器失效：

unordered_set<int> 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通常是首选。