blob: ef6598b63e3213580a62cccfd4ce5c4be08532be (
plain) (
blame)
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
|
# Two Sum
## Использование брутфорса
Самое просто решение. Сложность алгоритма `O(n^2)`.
```rust
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
for (i, x) in nums.iter().enumerate() {
for (j, y) in nums.iter().enumerate() {
if i != j && x + y == target {
return vec![i as i32, j as i32];
}
}
}
panic!("No solution found")
}
```
## Использование хэщ-таблицы
В этом решении используется хэш-таблица.
- Сложность: `O(n)`.
- Плюс: Скорость.
- Минус: Память.
```rust
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut hash: std::collections::HashMap<i32, usize> = std::collections::HashMap::new();
for (i, x) in nums.iter().enumerate() {
if hash.contains_key(x) {
return vec![*hash.get(x).unwrap() as i32, i as i32];
}
let res = target - x;
hash.insert(res, i);
}
panic!("No solution found")
}
```
|
