跳转至

两数之和

约 224 个字 48 行代码 预计阅读时间 1 分钟

题目描述

 给定一个数组nums和一个目标值target,找到一对下标i和j使得nums[i] + nums[j] == target。

思路

暴力求解

 先遍历\(i(i=[0,n]\))，再遍历\(j(j=[i+1,n])\),当满足条件nums[i] + nums[j] == target时，返回[i,j]即可。

 暴力求解的时间复杂度为：\(O(n^2)\)

Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#[cfg(test)]
pub mod test_1 {
    struct Solution;

    impl Solution {
        pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
            for i in 0..nums.len() {
                for j in i + 1..nums.len() {
                    if nums[i] + nums[j] == target {
                        return vec![i as i32, j as i32];
                    }
                }
            }
            return vec![-1, -1];
        }
    }

    #[test]
    fn test_p1() {
        assert_eq!(vec![0, 1], Solution::two_sum(vec![2, 7, 11, 15], 9));
    }
}

Hash 优化

 观察暴力求解的实现，我们第二层的 for 循环是为了找到一个j使得nums[i] + nums[j] == target。转换可以得到nums[j] = target-nums[i]。

 也就是说，我们可以在遍历nums[i]的时候，使用一个 map 存储nums[i]的信息，其中 key 就是nums[i],value 是i。当遍历到下一个i且满足map.container(target-nums[i]),我们所谓的j的下标就是map[target-nums[i]]。

 优化后的时间复杂度:\(O(n)\)，空间复杂度\(O(n)\);

Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#[cfg(test)]
pub mod test_1 {
    use std::collections::HashMap;

    struct Solution;

    impl Solution {
        pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
            let mut map = HashMap::<i32, i32>::new();
            for i in 0..nums.len() {
                if let Some(value) = map.get(&(target - nums[i])) {
                    return vec![i as i32, *value as i32];
                }
                map.insert(nums[i], i as i32);
            }
            return vec![-1, -1];
        }
    }

    #[test]
    fn test_p1() {
        assert_eq!(vec![1, 0], Solution::two_sum(vec![2, 7, 11, 15], 9));
    }
}