我正在解决有关leetcode的问题，以便在采访中更好地使用Rust。解决this problem的第一次尝试是，我想通过将a + b + c = 0，a和b存储在c中，然后将该solution: HashSet<i32>存储在另一个集合solution: HashSet<i32>中来表示三重态解solution_set: HashSet<HashSet<i32>> ]。疯狂吧？
该练习明确指出，多余的三元组不符合条件，因此，与其将三元组存储在solution: Vec<i32>中，否则顺序可能会更改Vec的哈希值，我想我应该将三元组存储在solution: HashSet<i32>中因此a，b和c的任何顺序都解析为相同的solution。此外，现在需要O(1)来验证solution_set: HashSet<HashSet<i32>>中是否已经存在三元组，而不是O(n)来检查替代项solution_set: Vec<HashSet<i32>>中是否存在三元组。最后，我知道返回值是Vec<Vec<i32>>，但这可以通过以下方法解决：drain()将solution: HashSet<i32>放入Vec<i32>，然后将结果Iter<Vec<i32>>排入Vec<Vec<i32>>。
[我认识到HashSet<T>并没有实现Hash，所以我决定尝试一下自己，现在，我在没有小河的地方划了桨。 🚣我查看了here，以了解有关为结构实现Hash的信息，并查看了here，以了解如何在我不拥有的结构上实现特征的信息，但是现在我重新实现了所有的函数句柄需要HashSet上的new()（drain()，insert()，HashSetWrapper等）。编译器也比较PartialEq等其他特征，因此我已经在此打开了pandora的盒子。我只是觉得这不是最“鲁棒”的方法。
此外，我知道正确实现哈希值并非易事，并且由于这是最佳实践中的一项工作，我希望获得一些帮助，以找出实现我的解决方案的最“鲁棒”的方式。我实际上还没有开始工作，但是到目前为止，这是我的代码：
use std::collections::HashSet;
use std::hash::{Hash, Hasher};
#[derive(PartialEq)]
struct HashSetWrapper<T>(HashSet<T>);
impl<T: Hash> HashSetWrapper<T> {
fn new() -> Self {
HashSetWrapper(HashSet::<T>::new())
}
fn insert(&self, value: T) {
self.0.insert(value);
}
}
impl<T: Hash> Hash for HashSetWrapper<T> {
fn hash<H: Hasher>(&self, state: &mut H) {
for value in &self.0 {
value.hash(state);
}
}
}
impl Solution {
pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut solution_set: HashSetWrapper<HashSet<i32>> = HashSetWrapper::new();
for (i, a) in nums[0..(nums.len() - 2)].iter().enumerate() {
for (j, b) in nums[i..(nums.len() - 1)].iter().enumerate() {
for c in nums[j..].iter() {
if a + b + c == 0 {
let mut temp = HashSet::<i32>::new();
temp.insert(*a);
temp.insert(*b);
temp.insert(*c);
solution_set.insert(temp); }
}
}
}
solution_set.drain().map(|inner_set| inner_set.drain().collect::<Vec<_>>()).collect::<Vec<_>>()
}
}
我仍然需要为我的包装器类实现一个drain()，但我什至不确定自己是否朝着正确的方向前进。您将如何解决这个问题？您将如何在Hash上实现HashSet？我想知道！
下面是编译器给我的错误：
Line 5, Char 26: binary operation `==` cannot be applied to type `std::collections::HashSet<T>` (solution.rs)
|
5 | struct HashSetWrapper<T>(HashSet<T>);
| ^^^^^^^^^^
|
= note: an implementation of `std::cmp::PartialEq` might be missing for `std::collections::HashSet<T>`
Line 5, Char 26: binary operation `!=` cannot be applied to type `std::collections::HashSet<T>` (solution.rs)
|
5 | struct HashSetWrapper<T>(HashSet<T>);
| ^^^^^^^^^^
|
= note: an implementation of `std::cmp::PartialEq` might be missing for `std::collections::HashSet<T>`
Line 9, Char 38: no function or associated item named `new` found for type `std::collections::HashSet<T>` in the current scope (solution.rs)
|
9 | HashSetWrapper(HashSet::<T>::new())
| ^^^ function or associated item not found in `std::collections::HashSet<T>`
|
= note: the method `new` exists but the following trait bounds were not satisfied:
`T : std::cmp::Eq`
Line 13, Char 16: no method named `insert` found for type `std::collections::HashSet<T>` in the current scope (solution.rs)
|
13 | self.0.insert(value);
| ^^^^^^ method not found in `std::collections::HashSet<T>`
|
= note: the method `insert` exists but the following trait bounds were not satisfied:
`T : std::cmp::Eq`
Line 28, Char 62: the trait bound `std::collections::HashSet<i32>: std::hash::Hash` is not satisfied (solution.rs)
|
8 | fn new() -> Self {
| ---------------- required by `HashSetWrapper::<T>::new`
...
28 | let mut solution_set: HashSetWrapper<HashSet<i32>> = HashSetWrapper::new();
| ^^^^^^^^^^^^^^^^^^^ the trait `std::hash::Hash` is not implemented for `std::collections::HashSet<i32>`
Line 38, Char 38: no method named `insert` found for type `HashSetWrapper<std::collections::HashSet<i32>>` in the current scope (solution.rs)
|
5 | struct HashSetWrapper<T>(HashSet<T>);
| ------------------------------------- method `insert` not found for this
...
38 | solution_set.insert(temp); }
| ^^^^^^ method not found in `HashSetWrapper<std::collections::HashSet<i32>>`
|
= note: the method `insert` exists but the following trait bounds were not satisfied:
`std::collections::HashSet<i32> : std::hash::Hash`
Line 42, Char 22: no method named `drain` found for type `HashSetWrapper<std::collections::HashSet<i32>>` in the current scope (solution.rs)
|
5 | struct HashSetWrapper<T>(HashSet<T>);
| ------------------------------------- method `drain` not found for this
...
42 | solution_set.drain().map(|inner_set| inner_set.drain().collect::<Vec<_>>()).collect::<Vec<_>>()
| ^^^^^ method not found in `HashSetWrapper<std::collections::HashSet<i32>>`
error: aborting due to 7 previous errors
我刚刚浏览了您的代码和人们的评论。我认为您对HashSet<i32>过于复杂，然后不得不为HashSetWrapper实现所有特征函数。一个简单的版本只是具有一个保留三元组的简单结构，并使其使用宏从Hash，Eq和PartialEq派生。为了自动执行去重复项，我们可以将三元组作为较早的注释进行排序。
以下是我的代码，在此建议的基础上，仍大致遵循您的three_sum实现的逻辑（它有一个bug，btw）。
#[derive(Hash, Eq, PartialEq, Debug)]
pub struct Triplet {
x: i32,
y: i32,
z: i32,
}
impl Triplet {
pub fn new(x: i32, y: i32, z: i32) -> Triplet {
let mut v = vec![x, y, z];
v.sort();
Triplet {
x: v[0],
y: v[1],
z: v[2],
}
}
pub fn to_vec(&self) -> Vec<i32> {
vec![self.x, self.y, self.z]
}
}
pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut res: HashSet<Triplet> = HashSet::new();
for (i, a) in nums[0..(nums.len() - 2)].iter().enumerate() {
for (j, b) in nums[i+1..(nums.len() - 1)].iter().enumerate() {
for c in nums[j+1..].iter() {
if a + b + c == 0 {
let triplet = Triplet::new(*a, *b, *c);
res.insert(triplet);
}
}
}
}
res.into_iter().map(|t| t.to_vec()).collect()
}
测试代码：
#[test]
fn test_three_sum() {
let result = vec![vec![-1, -1, 2], vec![-1, 0, 1]];
assert_eq!(three_sum(vec![-1, 0, 1, 2, -1, -4]), result)
}
结果：
running 1 test
test tests::test_three_sum ... ok