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

Algorithms
, ,

题目描述

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有 和为 0 且 不重复 的三元组。

示例

1
2
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

最初的写法（错误示例）

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
28
29
30
31
32
33
34
35
36
37
impl Solution {
    pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut nums = nums.clone();
        nums.sort();

        let mut result: Vec<Vec<i32>> = Vec::new();
        for (index, value) in nums.iter().enumerate() {
            if nums[index] == nums[index - 1] {
                continue;
            }

            let mut left_index = index + 1;
            let mut right_index = nums.len() - 1;

            while left_index < right_index {
                let sum = nums[index] + nums[left_index] + nums[right_index];

                if sum == 0 {
                    result.push(vec![nums[index], nums[left_index], nums[right_index]]);
                    left_index += 1;
                    right_index -= 1;
                    if nums[left_index] == nums[left_index - 1] {
                        left_index += 1
                    };
                    if nums[right_index] == nums[right_index + 1] {
                        right_index -= 1
                    };
                } else if sum < 0 {
                    left_index += 1;
                } else if sum > 0 {
                    right_index -= 1;
                }
            }
        }
        result
    }
}

反思

在最初的写法中，逻辑基本正确，但在处理重复元素时存在漏洞。具体问题如下：

  1. 当找到一个和为 0 的三元组后，left_index 和 right_index 同时向中间移动，但后续对重复元素的处理逻辑不完整。例如，当 nums[left_index] == nums[left_index - 1] 时，只简单地将 left_index 加 1，而没有继续检查是否仍然存在重复元素，导致部分重复三元组被加入结果中。
  2. 对于 right_index 的处理也有类似问题，没有彻底跳过所有重复元素。

错误示例

输入：nums = [-2,0,3,-1,4,0,3,4,1,1,1,-3,-5,4,0]
输出：[[-5,1,4],[-5,1,4],[-3,-1,4],[-3,0,3],[-2,-1,3],[-2,1,1],[-1,0,1],[-1,0,1],[0,0,0]]
预期结果：[[-5,1,4],[-3,-1,4],[-3,0,3],[-2,-1,3],[-2,1,1],[-1,0,1],[0,0,0]]

修正后的解法：正确处理重复元素

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
impl Solution {
    pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut nums = nums.clone();
        nums.sort();

        let mut result: Vec<Vec<i32>> = Vec::new();
        for (index, value) in nums.iter().enumerate() {
            if index > 0 && nums[index] == nums[index - 1] {
                continue;
            }

            let mut left_index = index + 1;
            let mut right_index = nums.len() - 1;

            while left_index < right_index {
                let sum = nums[index] + nums[left_index] + nums[right_index];

                if sum == 0 {
                    result.push(vec![nums[index], nums[left_index], nums[right_index]]);

                    // 跳过重复的左指针元素
                    left_index += 1;
                    while left_index < right_index && nums[left_index] == nums[left_index - 1] {
                        left_index += 1;
                    }

                    // 跳过重复的右指针元素
                    right_index -= 1;
                    while left_index < right_index && nums[right_index] == nums[right_index + 1] {
                        right_index -= 1;
                    }
                } else if sum < 0 {
                    left_index += 1;
                } else if sum > 0 {
                    right_index -= 1;
                }
            }
        }
        result
    }
}

修正点

  1. 在找到一个和为 0 的三元组后，对 left_index 和 right_index 的处理更加彻底：
    • 对于 left_index，在移动后继续检查是否与前一个元素相同，直到跳过所有重复元素。
    • 对于 right_index，在移动后继续检查是否与后一个元素相同，直到跳过所有重复元素。
  2. 这样可以确保不会重复添加相同的三元组。

优化过后的解法：减少内存占用

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
impl Solution {
    pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        if nums.len() < 3 {
            return vec![];
        }

        nums.sort_unstable();
        let mut result = Vec::new();

        for index in 0..nums.len() {
            if index > 0 && nums[index] == nums[index - 1] {
                continue;
            }

            let mut left = index + 1;
            let mut right = nums.len() - 1;

            while left < right {
                let sum = nums[index] + nums[left] + nums[right];
                if sum == 0 {
                    result.push(vec![nums[index], nums[left], nums[right]]);

                    // 跳过重复的左指针元素
                    left += 1;
                    while left < right && nums[left] == nums[left - 1] {
                        left += 1;
                    }

                    // 跳过重复的右指针元素
                    right -= 1;
                    while left < right && nums[right] == nums[right + 1] {
                        right -= 1;
                    }
                } else if sum < 0 {
                    left += 1;
                } else {
                    right -= 1;
                }
            }
        }

        result
    }
}

优化点

  1. 使用 sort_unstable 替代 sort，减少排序的开销。
  2. 原地排序 nums，减少 clone 带来的内存开销。

Rust 补充知识点

sort 与 sort_unstable

  • sort 是稳定排序，保证相等元素的相对顺序不变，但性能稍差。
  • sort_unstable 是不稳定排序，不保证相等元素的相对顺序，但性能更好。