【算法学习】一、两数之和（Rust 解法）

Algorithms
,

题目描述

给定一个整数数组 nums 和一个目标值 target，请在数组中找出 两个和为目标值 的元素，并返回它们的索引。

限制条件

  1. 每种输入只对应一个答案。
  2. 同一个元素不能重复使用。
  3. 可以按任意顺序返回答案。

示例

1
2
3
4
5
6
7
8
9
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：nums[0] + nums[1] = 2 + 7 = 9

输入：nums = [3,2,4], target = 6
输出：[1,2]

输入：nums = [3,3], target = 6
输出：[0,1]

最初的解决方法：暴力解法（双层循环）

执行时间：59 ms; 内存使用：2.39 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct Solution;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        for (index_i, i) in nums.iter().enumerate() {
            for (index_j, j) in nums.iter().enumerate() {
                if (i + j == target) && (index_i != index_j) {
                    return vec![index_i as i32, index_j as i32];
                }
            }
        }
        panic!("No solution found.");
    }
}

fn main() {
    println!("{:?}", Solution::two_sum(vec![3, 2, 4], 7))
}

改进后的解决方法：使用哈希表（HashMap）

执行时间：0 ms; 内存使用：2.43 MB

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
use std::collections::HashMap;

struct Solution;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut dict = HashMap::new();

        for (index, &num) in nums.iter().enumerate() {
            let complement = target - num;

            match dict.get(&complement) {
                Some(&j) => return vec![j, index as i32],
                None => {}
            }

            dict.insert(num, index as i32);
        }

        panic!("No solution found.");
    }
}

fn main() {
    println!("{:?}", Solution::two_sum(vec![3, 2, 4], 7))
}

改进点对比

项目 暴力解法 哈希表解法
时间复杂度 O(n²) O(n)
空间复杂度 O(1) O(n)
是否重复遍历 是 否

Rust 补充知识点

match 匹配语法详解

1
2
3
4
match dict.get(&complement) {
    Some(&j) => return vec![j, index as i32],
    None => {}
}
  • dict.get(&complement) 返回 Option<&i32>
    • 其是匹配模式，而不是匹配具体的数值
    • Some(&j) 是一种“模式匹配结构 + 解引用绑定”
    • dict.get(&complement) 返回的是 Option<&i32> 类型，其与底下的Some(x) 模式一致，会将其值赋给 j，而不是做传统的值比较（如 xxx == &j）。

等价写法

1
2
3
if let Some(&j) = dict.get(&complement) {
    return vec![j, index as i32];
}
  • if let 是 match 的简化语法，用于只关心 Some 的场景

模式匹配 vs 值匹配

Rust 的 match 语法强大之处在于它匹配的是结构（结构体、元组、枚举、引用），不是简单的值比较。例如：

1
2
3
4
5
6
let x = Some(&42);
match x {
    Some(&val) => println!("{}", val),  // 解引用 + 绑定
    None => println!("None"),
}