README.md

18. 4Sum

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:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] 

Example 2:

Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]] 

Constraints:

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

Solutions (Rust)

1. Solution

use std::collections::HashSet;implSolution{pubfnfour_sum(nums:Vec<i32>,target:i32) -> Vec<Vec<i32>>{let target = target asi64;letmut nums = nums.into_iter().map(|x| x asi64).collect::<Vec<_>>();letmut ret = HashSet::new(); nums.sort_unstable();for a in0..nums.len(){for b in a + 1..nums.len(){letmut c = b + 1;letmut d = nums.len() - 1;while c < d {let sum = nums[a] + nums[b] + nums[c] + nums[d];if sum == target {letmut quadruplets = vec![ nums[a]asi32, nums[b]asi32, nums[c]asi32, nums[d]asi32,]; quadruplets.sort_unstable(); ret.insert(quadruplets); c += 1; d -= 1;}elseif sum < target { c += 1;}else{ d -= 1;}}}} ret.into_iter().collect()}}