当前位置：首页 > news >正文

三数之和及unordered_set和set的使用区别

news 2025/11/24 19:41:28

一.算法介绍

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {//这种题直接作为一种常规的套路来做//第一主要先对nums排序是比较重要的，这样可以避免重复//第二就是使用set来进行判断是比较好的//第三就是vector只要顺序一样是可以自动排序，这个性质也比较重要vector<vector<int>>ans;sort(nums.begin(),nums.end());set<vector<int>>set;for(int i=0;i<nums.size()-2;i++){int left=i+1;int right=nums.size()-1;while(left<right){int sum=nums[i]+nums[left]+nums[right];if(sum==0){vector<int>ret={nums[i],nums[left],nums[right]};if(set.count(ret)==0){set.insert(ret);ans.push_back(ret);}left++;right--;}else if(sum>0){right--;}else{left++;}}}return ans;}
};

首先,我们检查输入数组 nums 的长度是否小于 3。如果是,那么肯定无法找到三个数之和为 0 的组合,所以直接返回一个空的结果数组 result。
接下来,我们对数组 nums 进行排序。这是一个非常关键的步骤,因为排序可以帮助我们更好地处理重复元素,并且可以利用双指针技巧来提高算法的效率。
我们使用一个 set 类型的变量 seen 来存储已经添加过的三元组组合。这样可以很方便地判断一个新的三元组组合是否已经存在。(这里因为在选择下一个的使用都是从i+1开始的，所以排序都是递增的，所以可以直接比较，不需要对vector进行从小排序)
接下来,我们使用一个外层循环遍历数组 nums,固定第一个数 nums[i]。在这个循环中,我们不需要像之前那样跳过重复的第一个数,因为我们将在后续的处理中避免生成重复的三元组。
在固定第一个数之后,我们使用两个指针 left 和 right 分别指向 i+1 和数组最后一个元素。然后我们通过移动这两个指针来寻找满足条件的第二个数和第三个数。
在寻找第二个数和第三个数的过程中,我们检查当前的三数之和是否等于 0。如果等于 0,我们将这个三元组组合存储在 triplet 变量中,并检查 seen 集合中是否已经存在该组合。如果不存在,则将其加入结果数组 result 并添加到 seen 集合中。
如果当前的三数之和小于 0,我们需要增大第二个数,所以将 left 向右移动。如果当前的三数之和大于 0,我们需要减小第三个数,所以将 right 向左移动。
最终,我们返回结果数组 result。

这个代码的时间复杂度为 O(n^2),其中 n 是输入数组 nums 的长度。第一层循环遍历数组需要 O(n)的时间,第二层使用双指针技巧寻找满足条件的第二个数和第三个数需要 O(n)的时间。总的时间复杂度为 O(n^2)。

这个代码的空间复杂度为 O(n),因为我们使用了一个 set 来存储已经添加过的三元组组合。

总的来说,这个代码利用了排序、双指针技巧和 set 的使用来提高算法的效率,并且通过避免生成重复的三元组组合来优化结果。它是一个非常高效和优雅的解决方案。

二.为何不可用`unordered_set<vector<int>>`

使用 unordered_set<vector> 不能正常工作的原因是因为 vector 没有定义默认的哈希函数。

在 C++ 中,unordered_set 依赖于哈希函数来计算元素的哈希值,并根据哈希值将元素存储在桶中。但是,vector 没有默认的哈希函数实现,因此无法被直接用作 unordered_set 的元素。

相反,set<vector> 可以正常工作,因为 set 使用元素的默认比较函数 operator< 来比较和排序元素。vector 有默认的比较运算符实现,因此可以被用作 set 的元素。

如果你想使用 unordered_set 来存储 vector,你需要自定义一个哈希函数。例如,你可以使用 std::hash 模板类并提供一个特化版本:

#include <functional>  
#include <unordered_set>  
#include <vector>  struct VectorHasher {  size_t operator()(const std::vector<int>& v) const {  std::hash<int> hasher;  size_t seed = 0;  for (int i : v) {  seed ^= hasher(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);  }  return seed;  }  
};  int main() {  std::unordered_set<std::vector<int>, VectorHasher> set;  // ...  
}