## 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.