leetcode_for_rust/cd0001_two_sum/
mod.rs

1//! Two Sum [leetcode: two_sum](https://leetcode.com/problems/two-sum/)
2//!
3//! Given an array of integers, return indices of the two numbers such that they add up to a specific target.
4//!
5//! You may assume that each input would have exactly one solution, and you may not use the same element twice.
6//!
7//! ***Example:***
8//!
9//! ```
10//! Given nums = [2, 7, 11, 15], target = 9,
11//!
12//! Because nums[0] + nums[1] = 2 + 7 = 9,
13//!
14//! return [0, 1].
15//! ```
16
17use std::collections::HashMap;
18/// # Solutions
19///
20/// # Approach 1: One-pass Hash Table
21///
22/// * Time complexity: O(n)
23///
24/// * Space complexity: O(n)
25///
26/// ```rust
27/// use std::collections::HashMap;
28///
29/// impl Solution {
30///     pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
31///         if nums.len() < 2 {
32///             return vec![];
33///         }
34///
35///         let mut positon = HashMap::new();
36///         for(i, num) in nums.iter().enumerate() {
37///             if positon.contains_key(num) {
38///                 return vec![positon[num] as i32, i as i32];
39///             } else {
40///                 positon.insert(target - num, i);
41///             }
42///         }
43///
44///         return vec![];
45///     }
46/// }
47/// ```
48///
49/// # Approach 2: Brute Force
50///
51/// * Time complexity: O(n^2)
52///
53/// * Space complexity: O(1)
54///
55/// ```rust
56/// impl Solution {
57///     pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
58///         if nums.len() < 2 {
59///             return vec![];
60///         }
61///
62///         let mut v: Vec<i32> = vec![];
63///         for i in 0..nums.len() {
64///             let n = target - nums[i];
65///             for j in (i+1)..nums.len() {
66///                 if n == nums[j] {
67///                     v.push(i as i32);
68///                     v.push(j as i32);
69///                     return v;
70///                 }
71///             }
72///         }
73///
74///         v
75///     }
76/// }
77///
78pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
79    if nums.len() < 2 {
80        return vec![];
81    }
82
83    let mut positon = HashMap::new();
84    for(i, num) in nums.iter().enumerate() {
85        if positon.contains_key(num) {
86            return vec![positon[num] as i32, i as i32];
87        } else {
88            positon.insert(target - num, i);
89        }
90    }
91
92    return vec![];
93}
leetcode_for_rust/cd0001_two_sum/mod.rs

leetcode_for_rust/cd0001_two_sum/
mod.rs
