0001. 两数之和 Two Sum

问题描述

方法1, Brute Force

这个方法比较直接, 就是遍历数组, 并遍历后面的每个元素, 求两者之和是否与 target 相等.

brute-force

因为有两层遍历, 这个方法的时间复杂度是 O(n^2).

#![allow(unused)]
fn main() {
// Brute Force
fn two_sum1(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let len = nums.len();
    for i in 0..(len - 1) {
        for j in (i + 1)..len {
            if i != j && nums[i] + nums[j] == target {
                return vec![i as i32, j as i32];
            }
        }
    }
    Vec::new()
}
}

方法2, 哈稀表

同样是需要遍历整个数组, 我们可以使用哈稀表缓存一下访问过的元素, 以加快查找元素的时间. 这个哈稀表用于记录元素值到它在数组中的索引值之间的关系.

但对于从哈稀表中查找, 我们可以进行一下优化, 即, 查找与当前元素之和为 target 的值, 如果找到, 就可以返回了.

hash-table

这个方法的时间复杂度是 O(n).

#![allow(unused)]
fn main() {
// 使用 Hash Table
fn two_sum2(nums: Vec<i32>, target: i32) -> Vec<i32> {
    use std::collections::HashMap;

    let mut visited: HashMap<i32, usize> = HashMap::with_capacity(nums.len());
    // 遍历整个数组.
    for (i, &item) in nums.iter().enumerate() {
        // 查找与当前元素之和为 target 的元素, 是否在哈稀表中.
        if let Some(&j) = visited.get(&(target - item)) {
            return vec![j as i32, i as i32];
        } else {
            visited.insert(item, i);
        }
    }

    Vec::new()
}
}