18. 4Sum Medium

1/**
2 * [18] 4Sum
3 *
4 * Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
5 *
6 * 0 <= a, b, c, d < n
7 * a, b, c, and d are distinct.
8 * nums[a] + nums[b] + nums[c] + nums[d] == target
9 *
10 * You may return the answer in any order.
11 *  
12 * Example 1:
13 *
14 * Input: nums = [1,0,-1,0,-2,2], target = 0
15 * Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
16 *
17 * Example 2:
18 *
19 * Input: nums = [2,2,2,2,2], target = 8
20 * Output: [[2,2,2,2]]
21 *
22 *  
23 * Constraints:
24 *
25 * 1 <= nums.length <= 200
26 * -10^9 <= nums[i] <= 10^9
27 * -10^9 <= target <= 10^9
28 *
29 */
30pub struct Solution {}
31
32// problem: https://leetcode.com/problems/4sum/
33// discuss: https://leetcode.com/problems/4sum/discuss/?currentPage=1&orderBy=most_votes&query=
34
35// submission codes start here
36
37impl Solution {
38    pub fn four_sum(nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
39        if nums.len() < 4 {
40            return vec![];
41        }
42        let mut data = nums.clone();
43        let mut result: Vec<Vec<i32>> = Vec::new();
44        data.sort();
45
46        for a in 0..data.len() - 3 {
47            if a > 0 && data[a] == data[a - 1] {
48                continue;
49            }
50
51            let remain = target - data[a];
52            for b in a + 1..data.len() - 2 {
53                if b > a + 1 && data[b] == data[b - 1] {
54                    continue;
55                }
56
57                let mut c = b + 1;
58                let mut d = data.len() - 1;
59                let remain_two = remain - data[b];
60                while c < d {
61                    let sum = data[d] + data[c];
62                    if sum == remain_two {
63                        result.push(vec![data[a], data[b], data[c], data[d]]);
64                        loop {
65                            c += 1;
66                            if c >= d || data[c - 1] != data[c] {
67                                break;
68                            }
69                        }
70                        loop {
71                            d -= 1;
72                            if d <= c || data[d + 1] != data[d] {
73                                break;
74                            }
75                        }
76                    } else if sum > remain_two {
77                        d -= 1;
78                    } else {
79                        c += 1;
80                    }
81                }
82            }
83        }
84
85        result
86    }
87}
88
89// submission codes end
90
91#[cfg(test)]
92mod tests {
93    use super::*;
94
95    #[test]
96    fn test_18() {
97        println!(
98            "Got result {:#?}",
99            Solution::four_sum(vec![1, 0, -1, 0, -2, 2], 0)
100        );
101        println!(
102            "Got result {:#?}",
103            Solution::four_sum(vec![2, 2, 2, 2, 2], 8)
104        );
105        println!(
106            "Got result {:#?}",
107            Solution::four_sum(
108                vec![0, 0, 0, 1000000000, 1000000000, 1000000000, 1000000000],
109                1000000000
110            )
111        );
112    }
113}
114