干净地修改hashmap中用于k-sum挑战的值。
刚开始学习锈病，这里有一个程序给我带来了一些痛苦，让我在铁锈中实现了。这在C++中是很容易实现的，但是Rust的借贷检查程序正在引起各种各样的麻烦。我的程序试图解决以下挑战：
您将得到一个整数数组
nums和一个整数k。在一个操作中，您可以从其和等于k的数组中选择两个数字，并将它们从数组中删除。返回可以对数组执行的最大操作数。
我使用的算法是显而易见的：
- 扫描输入，生成输入中每个整数计数的散列图。
- 在整数上循环，并对每个
n检查n和k - n的计数是否大于0(如果n和k-n相等，则超过1)。 - 如果是，则减少两个整数的计数并增加结果。
我在Rust中的实现如下，这似乎相当丑陋：
use std::collections::HashMap;
use std::collections::hash_map::Entry;
impl Solution {
pub fn max_operations(nums: Vec<i32>, k: i32) -> i32 {
let mut result = 0;
// Keep track of counts of each integer.
let mut counts = HashMap::<i32,i32>::new();
for n in nums.iter() {
let count = counts.entry(*n).or_insert(0);
*count += 1;
}
// Loop over each element and check if it has a matching pair to remove.
for n in nums.iter() {
if *n == k - *n {
if *counts.entry(*n).or_insert(0) < 2 {
continue;
}
result += 1;
*counts.entry(*n).or_insert(0) -= 2;
continue;
}
match counts.entry(*n) {
Entry::Occupied(o) => {
if *o.get() < 1 {
continue;
}
match counts.entry(k - *n) {
Entry::Occupied(o) => {
if *o.get() < 1 {
continue;
}
},
Entry::Vacant(_) => continue
}
},
Entry::Vacant(_) => continue
}
result += 1;
*counts.entry(*n).or_insert(0) -= 1;
*counts.entry(k - *n).or_insert(0) -= 1;
}
return result;
}
}我想做的是下面这样的内容，而不是match块和后面的所有内容：
if let counts.get(*n) > 0 && let counts.get(k - *n) > 0 {
*counts.entry(*n).or_insert(0) -= 1;
*counts.entry(k - *n).or_insert(0) -= 1;
}这是不可能的，它还会导致不必要的零插入到hashmap中的元素不存在。
Rust有没有用更紧凑的方式编写这样的代码？
回答 2
Code Review用户
发布于 2022-09-12 11:54:26
在for循环
中的分解
这两个for循环都定义为
for n in nums.iter() { .. }这使得n具有&i32类型，因此每次尝试使用它时，都必须使用*n取消对它的引用。由于i32实现了Copy，所以您可以使用
for &n in nums.iter() {
..
}这个脱结构是引用，所以n本身有i32类型，这使得它更符合人体工程学。
不必要的入口API
当您想要修改映射时，HashMap Entry API非常有用，并且不太了解键。一个完美的例子是如何使用or_insert初始化映射。
然而，在您的其余代码中，更符合人体工程学的方法是依赖get和Index，后者返回对给定键的HashMap中值的引用。
counts.get(key) // Returns Option<&i32> with Some(value) corresponding to the key if it exists, otherwise None.
counts[key] // Returns &i32 with the value, PANICS if the key does not exist.因为您知道所有nums都存在密钥，所以只需使用索引方法即可。对于k - n，使用counts.get()代替。下面的语句将代替match语句。
if let Some(&cnt) = counts.get(&(k - n)) {
if counts[&n] > 0 && cnt > 0 {
result += 1;
*counts.get_mut(&n).unwrap() -= 1;
*counts.get_mut(&(k - n)).unwrap() -= 1;
}
}注意，如果需要修改映射，则索引不起作用，因为HashMap没有实现IndexMut。您将需要使用get_mut代替，但您可以unwrap结果，因为我们知道键存在。
我们不能静态地向编译器证明get_mut(n)和get_mut(k - n)将对应于不同的键，因此我们需要跳一段舞来避免重叠的可变引用。
最终代码
fn max_operations(nums: Vec<i32>, k: i32) -> i32 {
let mut counts = HashMap::<i32, i32>::new();
for &n in nums.iter() {
*counts.entry(n).or_insert(0) += 1;
}
let mut result = 0;
for &n in nums.iter() {
if n == k - n {
if counts[&n] >= 2 {
result += 1;
*counts.get_mut(&n).unwrap() -= 2;
}
} else if let Some(&cnt) = counts.get(&(k - n)) {
if counts[&n] > 0 && cnt > 0 {
result += 1;
*counts.get_mut(&n).unwrap() -= 1;
*counts.get_mut(&(k - n)).unwrap() -= 1;
}
}
}
result
}Code Review用户
发布于 2022-09-12 12:19:36
您有一个很好的实现级别的阿普拉特的回答。我将讨论算法：
- 扫描输入，生成输入中每个整数计数的散列图。
- 在整数上循环，对于每个n，检查n和k的计数是否大于0(如果n和k相等，则大于1)。
- 如果是，则减少两个整数的计数并增加结果。
问题是可以从数组中删除多少对，而不是从数组中删除多少对。所以我们可以用min(count(n), count(k-n))来增加计数。如果我们不打算再看一遍的话，就不需要修改计数了。锈蚀不是我的语言，但我希望能够循环这些条目，忽略那些n > k - n，和特殊大写的n == k - n贡献count(n) / 2的总和。
顺便提一下，关于术语的一个注释: k-sum通常意味着“选择其和为给定值的k个数”。这是一种二和问题。
https://codereview.stackexchange.com/questions/276462
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号