blob: d82006732f6593cdf9ee71e9f148b91bee7732bd (
plain) (
tree)
|
|
# 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")
}
```
|