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}
leetcode_rust/problems/p000_0xx/p000_015.rs

leetcode_rust/problems/p000_0xx/
p000_015.rs
