3 ms·
First one I checked was `two_sum.rs` and it uses a `HashMap`: https://github.com/TheAlgorithms/Rust/blob/master/src/general/two_sum.rs https://github.com/TheAlg
by IshKebab 4y ago
First one I checked was `two_sum.rs` and it uses a `HashMap`: https://github.com/TheAlgorithms/Rust/blob/master/src/general/two_sum.rs 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!
- 988747 4y agoNo 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.
- IshKebab 4y agoOh yeah that is true. I am an idiot.
- zodiac 4y agoDepends on what you mean by "best". For e.g. comparison-based sorting will already cost O(n log n) time but the HashMap solution will run in O(n) HashMap operations.
- chrismorgan 4y agoEww, 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.