Rust在LeetCode上：解题与技能提升

Rust在LeetCode上：从Python转向系统思维

如果你访问了PythonLib，那么很可能你已经熟悉Python。你能够写出简洁的一行代码解决方案，并将动态类型视为理所当然。但世界在不断发展。在顶级公司（以及其他公司）的面试中，越来越多地要求用Rust编写代码。为什么？因为Rust是一种结合了C语言速度和内存安全性的语言，而LeetCode是磨练这项技能的理想场所。

在这篇文章中，我们不仅仅是快速浏览语法。我们将分析如何用Rust的范式思考算法问题，使用哪些数据结构，以及如何避免在borrow checker中迷失方向。开始吧！

为什么在LeetCode上使用Rust既是挑战又是优势？

LeetCode上的大多数解决方案都是用Python或Java编写的。而Rust迫使你思考内存、所有权和生命周期。这看起来很难，但这正是让你成为更强工程师的原因。用Rust解题时，你会自动学习：

\n
• 所有权系统（Ownership）——该语言的主要特点。
\n
• 借用（Borrowing）以及可变/不可变引用。
\n
• 高效的迭代器，无需额外分配内存。
\n
• 使用Option和Result代替异常处理。
\n

如果你是从Python转过来的，前10道题可能会让你觉得是种折磨。但当你理解了编译器如何保护你免受null pointer和数据竞争的影响时，你会爱上这门语言。

开始之前需要学习什么？

在投身于题海之前，让我们先分析一下工具集。没有它，你会像用宏写C++一样低效且痛苦。

1. 迭代器和闭包（Closures）

在Rust中，迭代器不仅仅是for循环。它是一个强大的函数式工具。与其写for i in 0..vec.len()，不如学会使用.iter()、.map()、.filter()、.fold()。

// Python: [x*2 for x in list if x > 0]\n// Rust:\nlet result: Vec<i32> = list.iter()\n    .filter(|&x| *x > 0)\n    .map(|x| x * 2)\n    .collect();

这段代码不仅更短，而且运行更快，因为迭代器是惰性的，编译器会将其优化为线性循环。

2. HashMap和BTreeMap

对于计数频率的题目（例如“Two Sum”或“Group Anagrams”），HashMap是你最好的朋友。但请记住：在Rust中，向HashMap插入数据需要拥有键的所有权。如果你使用&str，你将不得不克隆字符串或使用String。

use std::collections::HashMap;\n\nfn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {\n    let mut map = HashMap::new();\n    for (i, &num) in nums.iter().enumerate() {\n        let complement = target - num;\n        if let Some(&j) = map.get(&complement) {\n            return vec![j as i32, i as i32];\n        }\n        map.insert(num, i);\n    }\n    vec![]\n}

请注意：enumerate()返回一个元组(usize, &i32)。我们使用&num来解引用。

3. Vec和切片

Vec是一个动态数组。但在LeetCode题目中，经常需要处理子数组。为此，请使用切片&[T]。它们不需要复制，并允许将数组的一部分传递给函数。

fn max_subarray_sum(arr: &[i32]) -> i32 {\n    let mut max_ending = arr[0];\n    let mut max_so_far = arr[0];\n    for &x in arr[1..].iter() {\n        max_ending = std::cmp::max(x, max_ending + x);\n        max_so_far = std::cmp::max(max_so_far, max_ending);\n    }\n    max_so_far\n}

前5个典型错误