字数

341 字

阅读时间

2 分钟

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

暴力解

遍历两遍nums做匹配

时间复杂度: O(n^2)

空间复杂度: O(1)

优解

使用HashMap来进行匹配操作。每次匹配的时候可通过键值对应的方式直接获知值的查询结果，无须遍历

时间复杂度: O(n)

空间复杂度: O(n)

暴力做法每次拿两个数出来相加，和 target 比较，那么花费 O(1) 的时间，只获取了 O(1) 的信息。 而哈希表做法，每次查询都能知道 O(n) 个数中是否有 target − nums[j]，那么花费 O(1) 的时间，就获取了 O(n) 的信息。

——灵茶山艾府

use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut idx = HashMap::new();
        for (j, &x) in nums.iter().enumerate() { // enumerate枚举
            if let Some(&i) = idx.get(&(target - x)) { // 使用Some(&)拆出i
                return vec![i as i32, j as i32];
            }
            idx.insert(x,j);
        }
        unreachable!();
    }
}

贡献者

Kiracoon

页面历史

最后编辑于 3 个月前

查看完整历史

e29955d-LeetCode - 1