DeepSeek LeetCode 15.三数之和 Rust实现

下面是 LeetCode 15「三数之和」的 Rust 实现使用排序 双指针时间复杂度 O(n²)。rustimpl Solution {pub fn three_sum(mut nums: Veci32) - VecVeci32 {let mut ans: VecVeci32 Vec::new();let n nums.len();if n 3 {return ans;}// 先排序方便双指针和去重nums.sort_unstable();for i in 0..n - 2 {// 跳过重复的第一个数if i 0 nums[i] nums[i - 1] {continue;}// 如果当前数已经大于 0后面不可能再凑出 0if nums[i] 0 {break;}let (mut left, mut right) (i 1, n - 1);while left right {let sum nums[i] nums[left] nums[right];if sum 0 {ans.push(vec![nums[i], nums[left], nums[right]]);// 跳过重复的 left 和 rightwhile left right nums[left] nums[left 1] {left 1;}while left right nums[right] nums[right - 1] {right - 1;}left 1;right - 1;} else if sum 0 {left 1;} else {right - 1;}}}ans}}思路1. 先对数组排序。2. 固定第一个数 nums[i]然后用双指针 left 和 right 在剩余区间内寻找另外两个数。3. 如果三数之和等于 0记录结果并跳过重复的 left 和 right。4. 如果和小于 0说明需要增大左指针右移如果和大于 0右指针左移。5. 外层循环中跳过重复的 nums[i]避免重复三元组。复杂度· 时间复杂度O(n²)· 空间复杂度O(log n)排序栈空间返回结果不计入额外空间。