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}