Re:All Algorithms Implemented in Rust
by chrismorgan on Monday August 22, 2022 @04:50AM
(#32548927)
Eww, eww, eww, why is that returning Vec<i32>? It should clearly be returning Option<(usize, usize)>.
pub fn two_sum(nums: Vec<i32>, target: i32) -> Option<(usize, usize)> {
let mut hash_map: HashMap<i32, i32> = HashMap::new();
for (i, item) in nums.iter().enumerate() {
match hash_map.get(&(target - item)) {
Some(value) => return Some((i, *value)),
None => hash_map.insert(*item, i);
}
}
None
}
If the caller wants to do something weird like converting the index to an i32 (which immediately means you can’t handle 2³¹ or more (~2 billion) items) or turning it into a zero-or-two-element Vec (which is inefficient and far easier to make mistakes with), they can do that themselves.This speaks very clearly to me that either there is some unreasonable constraint in place that I don’t immediately see, or neither the author nor the reviewer was at all competent in Rust.
No expert on algorithms, but:
Sorting an array is O(n*log(n))
Hashmap operations are constant time, and walking through array to put stuff in it is O(n)
So, implementation based on Hashmap should be slightly faster. It requires extra memory, though.
Oh yeah that is true. I am an idiot.
Surely the best way is to sort the numbers and then walk from both ends?
Nice work anyway!