15. 3Sum Medium

1/**
2 * [15] 3Sum
3 *
4 * Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] 
5 * such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
6 * Notice that the solution set must not contain duplicate triplets.
7 *  
8 * Example 1:
9 * Input: nums = [-1,0,1,2,-1,-4]
10 * Output: [[-1,-1,2],[-1,0,1]]
11 * Example 2:
12 * Input: nums = []
13 * Output: []
14 * Example 3:
15 * Input: nums = [0]
16 * Output: []
17 *  
18 * Constraints:
19 * 
20 * 0 <= nums.length <= 3000
21 * -10^5 <= nums[i] <= 10^5
22 * 
23 */
24pub struct Solution {}
25
26// problem: https://leetcode.com/problems/3sum/
27// discuss: https://leetcode.com/problems/3sum/discuss/?currentPage=1&orderBy=most_votes&query=
28
29// submission codes start here
30
31impl Solution {
32    pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
33        let mut result: Vec<Vec<i32>> = Vec::new();
34        if nums.len() < 3 {return result;}
35        let mut data = nums.clone();
36        data.sort();
37
38        for i in 0..data.len() - 2 {
39            if i != 0 && data[i] == data[i - 1] {
40                continue;
41            }
42
43            let mut s = i + 1;
44            let mut e = data.len() - 1;
45            let sum = -data[i];
46            while s < e {
47                if data[s] + data[e] == sum {
48                    result.push(vec![data[i], data[s], data[e]]);
49                    while s < e && data[s] == data[s + 1] {s += 1}
50                    while s < e && data[e] == data[e - 1] {e -= 1}
51                    s += 1; e -= 1;
52                } else if data[s] + data[e] > sum {
53                    e -= 1;
54                } else {
55                    s += 1;
56                }
57            }
58        }
59
60        result
61    }
62}
63
64// submission codes end
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69
70    #[test]
71    fn test_15() {
72        println!("got {:#?}", Solution::three_sum(vec![-1,0,1,2,-1,-4,1]));
73    }
74}
75