leetcode_rust/problems_cn/p000_0xx/
p000_015.rs

1//! # 问题描述
2//!
3//! 给你一个整数数组 `nums` ，判断是否存在三元组 `[nums[i], nums[j], nums[k]]` 满足
4//! `i != j`、`i != k` 且 `j != k` ，同时还满足 `nums[i] + nums[j] + nums[k] == 0`。
5//! 请你返回所有和为 `0` 且不重复的三元组。
6//! 
7//! 注意：答案中不可以包含重复的三元组。
8//! 
9//! 示例 1：
10//! 
11//! ```plain
12//! 输入：nums = [-1,0,1,2,-1,-4]
13//! 输出：[[-1,-1,2],[-1,0,1]]
14//! 解释：
15//! nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
16//! nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
17//! nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
18//! 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
19//! 注意，输出的顺序和三元组的顺序并不重要。
20//! ```
21//! 
22//! 示例 2：
23//! 
24//! ```plain
25//! 输入：nums = [0,1,1]
26//! 输出：[]
27//! 解释：唯一可能的三元组和不为 0 。
28//! ```
29//! 
30//! 示例 3：
31//! 
32//! ```plain
33//! 输入：nums = [0,0,0]
34//! 输出：[[0,0,0]]
35//! 解释：唯一可能的三元组和为 0 。
36//! ``` 
37//! 
38//! 提示：
39//! 
40//! - `3 $\leqslant$ nums.length $\leqslant$ 3000`
41//! - `$-10^{5} \leqslant$ nums[i] $\leqslant 10^{5}$`
42//! 
43//! 来源：<https://leetcode.cn/problems/3sum/>
44
45////////////////////////////////////////////////////////////////////////////////
46
47/// 三数之和
48///
49/// # 参数
50/// * `nums` - 输入数字序列
51pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
52    algorithm_2(nums)
53}
54
55/// Personal implementation
56///
57/// # Arguments
58/// * `nums` - input numbers to check for triplets.
59fn algorithm_2(nums: Vec<i32>) -> Vec<Vec<i32>> {
60    let mut res: Vec<Vec<i32>> = vec![];
61
62    if nums.len() >= 3 {
63        let mut sorted_nums = nums.clone();
64        sorted_nums.sort();
65
66        let mut i = 0;
67        while i < sorted_nums.len() - 1 {
68            let a = sorted_nums[i];
69
70            if i > 0 && sorted_nums[i - 1] == sorted_nums[i] {
71                i += 1;
72                continue;
73            }
74
75            let mut j = i + 1;
76
77            while j < sorted_nums.len() - 1 {
78                let b = sorted_nums[j];
79
80                if a + b > 0 {
81                    break;
82                }
83
84                if i + 1 < j && b == sorted_nums[j - 1] {
85                    // Already searched last time, continue
86                    j += 1;
87                    continue;
88                }
89
90                let mut start = 0;
91                let mut end = sorted_nums[(j + 1)..].len() - 1;
92
93                while start < end {
94                    let middle = (end + start) / 2;
95                    if sorted_nums[(j + 1)..][middle] < -a - b {
96                        start = middle + 1;
97                    } else {
98                        end = middle;
99                    }
100                }
101
102                let k = j + 1 + start;
103
104                let c = sorted_nums[k];
105
106                if a + b + c == 0 {
107                    res.push(vec![a, b, c]);
108                }
109                j += 1;
110            }
111
112            i += 1;
113        }
114    }
115
116    res
117}
leetcode_rust/problems_cn/p000_0xx/p000_015.rs

leetcode_rust/problems_cn/p000_0xx/
p000_015.rs
