思路： 思路同3sum, 先排序，分别对前两个遍历，后两个从两边逼近
O(n^3)
Python:
class Solution:
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
# 5 star,
nums.sort()
rs = set()
for i in range(len(nums) - 3):
j = i + 1
while j < len(nums) - 2:
left = j + 1
right = len(nums) - 1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total > target:
right -= 1
elif total < target:
left += 1
else:
rs.add((nums[i], nums[j], nums[left], nums[right]))
left += 1
j += 1
return list(rs)Go:
func fourSum(nums []int, target int) [][]int {
var ret [][]int
length := len(nums)
sort.Ints(nums)
for first:=0; first < length-3; first++ {
if first == 0 || nums[first] > nums[first-1] { //防止第一个元素重复
for second:=first+1; second < length-2;second++ {
if second == first+1 || nums[second] > nums[second-1] { //防止第二个元素重复
left, right := second+1, length-1
for left < right {
curSum := nums[first] + nums[second] + nums[left] + nums[right]
if curSum > target {
right--
} else if curSum < target {
left++
} else {
ret = append(ret, []int{nums[first], nums[second], nums[left], + nums[right]})
left++
for left <= right && nums[left] == nums[left-1] {left++} //防止第三个元素重复，前三项不重复，第四项肯定不会重复了
}
}
}
}
}
}
return ret
}