leetcode_rust/problems/p000_0xx/p000_015.rs
1//! # Description
2//!
3//! Given an integer array `nums`, return all the triplets `[nums[i], nums[j],
4//! nums[k]]` such that `i != j`, `i != k`, and `j != k`, and `nums[i] + nums[j] + nums[k] == 0`.
5//!
6//! Notice that the solution set must not contain duplicate triplets.
7//!
8//! Example 1:
9//!
10//! ```plain
11//! Input: nums = [-1,0,1,2,-1,-4]
12//! Output: [[-1,-1,2],[-1,0,1]]
13//! Explanation:
14//! nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
15//! nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
16//! nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
17//! The distinct triplets are [-1,0,1] and [-1,-1,2].
18//! Notice that the order of the output and the order of the triplets does not matter.
19//! ```
20//!
21//! Example 2:
22//!
23//! ```plain
24//! Input: nums = [0,1,1]
25//! Output: []
26//! Explanation: The only possible triplet does not sum up to 0.
27//! ```
28//!
29//! Example 3:
30//!
31//! ```plain
32//! Input: nums = [0,0,0]
33//! Output: [[0,0,0]]
34//! Explanation: The only possible triplet sums up to 0.
35//! ```
36//!
37//! Constraints:
38//!
39//! - `3 $\leqslant$ nums.length $\leqslant$ 3000`
40//! - `-105 $\leqslant$ nums[i] $\leqslant$ 105`
41//!
42//! Sources: <https://leetcode.com/problems/3sum/>
43
44////////////////////////////////////////////////////////////////////////////////
45
46/// 3Sum
47///
48/// # Arguments
49/// * `nums` - input number pairs
50pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
51 algorithm_2(nums)
52}
53
54/// Personal implementation
55///
56/// # Arguments
57/// * `nums` - input numbers to check for triplets.
58fn algorithm_2(nums: Vec<i32>) -> Vec<Vec<i32>> {
59 let mut res: Vec<Vec<i32>> = vec![];
60
61 if nums.len() >= 3 {
62 let mut sorted_nums = nums.clone();
63 sorted_nums.sort();
64
65 let mut i = 0;
66 while i < sorted_nums.len() - 1 {
67 let a = sorted_nums[i];
68
69 if i > 0 && sorted_nums[i - 1] == sorted_nums[i] {
70 i += 1;
71 continue;
72 }
73
74 let mut j = i + 1;
75
76 while j < sorted_nums.len() - 1 {
77 let b = sorted_nums[j];
78
79 if a + b > 0 {
80 break;
81 }
82
83 if i + 1 < j && b == sorted_nums[j - 1] {
84 // Already searched last time, continue
85 j += 1;
86 continue;
87 }
88
89 let mut start = 0;
90 let mut end = sorted_nums[(j + 1)..].len() - 1;
91
92 while start < end {
93 let middle = (end + start) / 2;
94 if sorted_nums[(j + 1)..][middle] < -a - b {
95 start = middle + 1;
96 } else {
97 end = middle;
98 }
99 }
100
101 let k = j + 1 + start;
102
103 let c = sorted_nums[k];
104
105 if a + b + c == 0 {
106 res.push(vec![a, b, c]);
107 }
108 j += 1;
109 }
110
111 i += 1;
112 }
113 }
114
115 res
116}
117
118/// Sample algorithm implementation from LeetCode (fastest)
119///
120/// # Arguments
121/// * `nums` - input numbers to check for triplets.
122#[allow(dead_code)]
123pub fn algorithm_1(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
124 let mut res = vec![];
125 let len = nums.len();
126 nums.sort_unstable();
127
128 for i in 0..len {
129 let left = nums[i];
130
131 if i > 0 && nums[i - 1] == left {
132 continue;
133 }
134
135 let mut middle = i + 1;
136 let mut right = len - 1;
137
138 while middle < right {
139 let curr_sum = left + nums[middle] + nums[right];
140
141 if curr_sum == 0 {
142 res.push(vec![left, nums[middle], nums[right]]);
143 middle += 1;
144
145 while middle < right && nums[middle - 1] == nums[middle] {
146 middle += 1;
147 }
148
149 right -= 1;
150 } else if curr_sum < 0 {
151 middle += 1;
152 } else {
153 right -= 1;
154 }
155 }
156 }
157
158 res
159}
160
161#[cfg(test)]
162mod tests {
163 use super::three_sum;
164
165 #[test]
166 fn test_three_sum() {
167 assert_eq!(
168 vec![vec![-1, -1, 2], vec![-1, 0, 1]],
169 three_sum(vec![-1, 0, 1, 2, -1, -4])
170 );
171 assert_eq!(Vec::<Vec<i32>>::from(vec![]), three_sum(vec![0, 1, 1]));
172 assert_eq!(vec![vec![0, 0, 0]], three_sum(vec![0, 0, 0]));
173 assert_eq!(vec![vec![0, 0, 0]], three_sum(vec![0, 0, 0, 0]));
174 }
175}