0
\$\begingroup\$

Started learning Rust by solving LeetCode problems as they involve all the standard data structures of the language. I have the following standard hash table solution to the two-sum problem:

use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut positions = HashMap::<i32,usize>::new();

        for (pos, n) in nums.iter().enumerate() {
            positions.insert(*n, pos);
        }

        for (pos, n) in nums.iter().enumerate() {
            if let Some(p) = positions.get(&(target - *n)) {
                if *p != pos {
                    return vec![pos as i32, *p as i32];
                }
            }
        }

        return vec![];
    }
}

In other words, the code returns two distinct indices into the vector such that the corresponding entries sum up to target.

The signature of the function is given by the platform. Since we are returning indices into the array, the return type should obviously be Vec<usize>, so this is a dumb choice. Having to live with that, I'm trying to figure out two things:

  1. Since integers are trivial to copy, is there a way to write the code without having to deal with references?
  2. HashMap::get() seems to want a reference as its parameter. Is there a way to avoid the ugly &(target - *n) when looking up positions in the hash table?
  3. Any other Rust tips for making the code cleaner or more idiomatic?
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

welcome.

    • You can use .into_iter() to consume the vector and return the numbers by value instead of by reference, this will only work in the last place you use the vector.
    • You can also use .copied() on an iterator where the inner type implements Copy, this way you remove the referencing.
    • When matching you can match to a pattern with build in dereferencing if let Some(&p) = ... here p is usize instead of &usize.
  1. Yes it does. You can also see this in action in the documentation.
    • The last line can be just Vec::new() (or vec![]) instead of return vec![];.
    • The first loop can be rewritten as follows: positions.extend(nums.iter().enumerate().map(|(pos, n)| (*n, pos)));.
    • You do not have to write out the HashMap type, but it can help in reasoning about the code.

Here is the function again with the above mentioned changes.

pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut positions = HashMap::<i32, usize>::new();

    positions.extend(nums.iter().copied().enumerate().map(|(pos, n)| (n, pos)));

    for (pos, n) in nums.iter().copied().enumerate() {
        if let Some(&p) = positions.get(&(target - n)) {
            if p != pos {
                return vec![pos as i32, p as i32];
            }
        }
    }

    Vec::new()
}
\$\endgroup\$
2
  • \$\begingroup\$ Good suggestions here! Had not noticed that if let dereference when skimming the Rust book. Will dig into the generated assembly code next to understand what the impact is on code generation. \$\endgroup\$ May 27 at 9:56
  • 1
    \$\begingroup\$ I'd suggest using let positions: HashMap<i32, usize> = nums.iter().copied().enumerate().map(|(pos, n)| (n, pos)).collect(); rather then extend. \$\endgroup\$ Jun 4 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.