# 18. 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]
]
``````

Tags: Array, Hash Table, Two Pointers

## 题解

### 思路1

``````func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
var res [][]int
for i := 0; i < len(nums)-3; i++ {
if i != 0 && nums[i] == nums[i-1] {
continue
}
threeSum(&res, nums[i], nums[i+1:], target-nums[i])
}
return res
}

func threeSum(res *[][]int, first int, nums []int, target int) {
nlen := len(nums)
for i := 0; i < nlen-2; i++ {
if i != 0 && nums[i] == nums[i-1] {
continue
}

left, right := i+1, nlen-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum == target {
*res = append(*res, []int{first, nums[i], nums[left], nums[right]})
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
} else if sum < target {
for left < right && nums[left] == nums[left+1] {
left++
}
left++
} else {
for left < right && nums[right] == nums[right-1] {
right--
}
right--
}
}
}
}
``````

```