15. 3Sum
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = [] Output: []
Example 3:
Input: nums = [0] Output: []
Constraints:
0 <= nums.length <= 3000-105 <= nums[i] <= 105
Rust Solution
struct Solution;
impl Solution {
fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut res: Vec<Vec<i32>> = vec![];
let n = nums.len();
if n < 3 {
return res;
}
nums.sort_unstable();
for i in 0..n - 2 {
let a = nums[i];
if nums[i] > 0 {
break;
}
if i > 0 && nums[i] == nums[i - 1] {
continue;
}
let mut j = i + 1;
let mut k = n - 1;
while j < k {
let b = nums[j];
let c = nums[k];
let sum = a + b + c;
if sum == 0 {
res.push(vec![a, b, c]);
j += 1;
k -= 1;
while j < k && nums[j] == nums[j - 1] {
j += 1;
}
while j < k && nums[k] == nums[k + 1] {
k -= 1;
}
} else {
if sum < 0 {
j += 1;
} else {
k -= 1;
}
}
}
}
res
}
}
#[test]
fn test() {
let nums = vec![-1, 0, 1, 2, -1, -4];
let res: Vec<Vec<i32>> = vec_vec_i32![[-1, -1, 2], [-1, 0, 1]];
assert_eq!(Solution::three_sum(nums), res);
let nums = vec![-2, 0, 1, 1, 2];
let res: Vec<Vec<i32>> = vec_vec_i32![[-2, 0, 2], [-2, 1, 1]];
assert_eq!(Solution::three_sum(nums), res);
}
Having problems with this solution? Click here to submit an issue on github.