给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
python
# 四数之和
class Solution:
def fourSum(self, nums:[int], target: int) -> [int]:
"""
排序加双指针，参考三数之和，时间O(n^3 + nlogn), 空间O(n)
思路：
算法流程：
:param nums:
:param target:
:return:
"""
res = []
if not nums or len(nums) < 4:
return res
n = len(nums)
nums.sort()
for first in range(n-3):
if first > 0 and nums[first] == nums[first-1]: # 检查重复
continue
for second in range(first+1, n-2):
if second > first+1 and nums[second] == nums[second-1]: # 检查重复
continue
left, right = second+1, n-1
while left < right:
target_ = nums[first] + nums[second] - target
if target_ < -(nums[left] + nums[right]): # python不考虑溢出
left += 1
elif target_ > -(nums[left] + nums[right]):
right -= 1
else:
res.append([nums[first], nums[second], nums[left], nums[right]])
while left < right and nums[left+1]==nums[left]: # 检查重复
left += 1
while left < right and nums[right-1] == nums[right]: # 检查重复
right -= 1
left += 1
right -= 1
return res
if __name__ == "__main__":
nums = [2,4,6,2,9,-12,43,5,-7,21,-20,4]
nums1 = [2,2,2,2,2,2]
test = Solution()
print(test.fourSum(nums, 0))
print(test.fourSum(nums1, 8))
glang
func fourSum(nums []int, target int) [][]int {
res := [][]int{}
if len(nums) < 4 {
return res
}
n := len(nums)
sort.Ints(nums)
for first := 0; first < n-3; first++ {
if first > 0 && nums[first] == nums[first-1] {
continue
}
for second := first + 1; second < n-2; second++ {
if second > first+1 && nums[second] == nums[second-1] {
continue
}
left, right := second+1, n-1
for left < right {
if nums[first]+nums[second]-target < -(nums[left] + nums[right]) {
left++
} else if nums[first]+nums[second]-target > -(nums[left] + nums[right]) {
right--
} else {
res = append(res, []int{nums[first], nums[second], nums[left], nums[right]})
for left < right && nums[left+1] == nums[left] {
left++
}
for left < right && nums[right-1] == nums[right] {
right--
}
left++
right--
}
}
}
}
return res
}