4Sum
Description
Given an array nums
of n integers and an integer target
, are there elements a, b, c, and d in nums
such that a + b + c + d = target
? Find all unique quadruplets in the array which gives the sum of target
.
Note:
The solution set must not contain duplicate quadruplets.
Example:
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
Solution(javascript)
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
const fourSum = function (nums, target) {
const result = {}
const map = {}
nums.sort((a, b) => a - b)
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length; j++) {
const sum = nums[i] + nums[j]
if (map[target - sum]) {
map[target - sum].forEach(([a, b]) => {
const set = new Set([a, b, i, j])
if (set.size === 4) {
const current = [nums[a], nums[b], nums[i], nums[j]].sort((a, b) => a - b)
result[current.join(',')] = current
}
})
}
if (map[sum]) {
map[sum].push([i, j])
} else {
map[sum] = [[i, j]]
}
}
}
return Object.values(result)
}