1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

//! Two Sum [leetcode: two_sum](https://leetcode.com/problems/two-sum/)
//!
//! Given an array of integers, return indices of the two numbers such that they add up to a specific target.
//!
//! You may assume that each input would have exactly one solution, and you may not use the same element twice.
//!
//! ***Example:***
//!
//! ```
//! Given nums = [2, 7, 11, 15], target = 9,
//!
//! Because nums[0] + nums[1] = 2 + 7 = 9,
//!
//! return [0, 1].
//! ```

use std::collections::HashMap;
/// # Solutions
///
/// # Approach 1: One-pass Hash Table
///
/// * Time complexity: O(n)
///
/// * Space complexity: O(n)
///
/// ```rust
/// use std::collections::HashMap;
///
/// impl Solution {
///     pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
///         if nums.len() < 2 {
///             return vec![];
///         }
///
///         let mut positon = HashMap::new();
///         for(i, num) in nums.iter().enumerate() {
///             if positon.contains_key(num) {
///                 return vec![positon[num] as i32, i as i32];
///             } else {
///                 positon.insert(target - num, i);
///             }
///         }
///
///         return vec![];
///     }
/// }
/// ```
///
/// # Approach 2: Brute Force
///
/// * Time complexity: O(n^2)
///
/// * Space complexity: O(1)
///
/// ```rust
/// impl Solution {
///     pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
///         if nums.len() < 2 {
///             return vec![];
///         }
///
///         let mut v: Vec<i32> = vec![];
///         for i in 0..nums.len() {
///             let n = target - nums[i];
///             for j in (i+1)..nums.len() {
///                 if n == nums[j] {
///                     v.push(i as i32);
///                     v.push(j as i32);
///                     return v;
///                 }
///             }
///         }
///
///         v
///     }
/// }
///
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    if nums.len() < 2 {
        return vec![];
    }

    let mut positon = HashMap::new();
    for(i, num) in nums.iter().enumerate() {
        if positon.contains_key(num) {
            return vec![positon[num] as i32, i as i32];
        } else {
            positon.insert(target - num, i);
        }
    }

    return vec![];
}