First one I checked was `two_sum.rs` and it uses a `HashMap`: https://github.com/TheAlgorithms/Rust/blob/master/src/genera...
Surely the best way is to sort the numbers and then walk from both ends?
Nice work anyway!
Surely the best way is to sort the numbers and then walk from both ends?
Nice work anyway!
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
}
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.
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.