难度中等997
给你一个由
n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、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
有了前面的两数之和的基础，我首先想到的利用双指针的方法来解决这个问题；整个调试过程真的很艰难，最后在自己的努力下终于AC了（虽然时空复杂度并不是很优秀）。
调试过程主要要注意一下几点：
我的代码：
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
result_ls = []
len_nums = len(nums)
#线排序一下，这样就可使用双指针的方法
nums.sort()
#print(nums)
f1 = 0
f2 = 0
for element1 in range(len_nums - 3):
if f1 > 0:
f1 -= 1
continue
f2 = 0
for element2 in range(element1 + 1, len_nums - 2):
left = element2 + 1
right = len_nums - 1
if f2 > 0:
f2 -= 1
continue
while(left < right):
sum = nums[element1] + nums[element2] + nums[left] + nums[right]
#print(element1, element2, left, right)
if sum == target:
#print('resut',element1, element2, left, right)
t_ls = []
t_ls.append(nums[element1])
t_ls.append(nums[element2])
t_ls.append(nums[left])
t_ls.append(nums[right])
result_ls.append(t_ls)
left += 1
while left < right and nums[left] == nums[left - 1]:
#print('left', left)
left += 1
# 特殊情况就是留给right的一个值他并没有使用，而是继续自己使用的情况，那就是重复值
sum_new = nums[element1] + nums[element2] + nums[left] + nums[right]
if left + 1 == right and nums[left] == nums[left + 1] and (sum == target or sum_new > target):
break
elif sum < target:
left += 1
#print('-2',left,right)
while left + 1 < right and nums[left] == nums[left - 1]:
#print('left', left)
left += 1
# 特殊情况就是留给right的一个值他并没有使用，而是继续自己使用的情况，那就是重复值
sum_new = nums[element1] + nums[element2] + nums[left] + nums[right]
if left + 1 == right and nums[left] == nums[left + 1] and (sum == target or sum_new > target):
break
else:
right -= 1
#print('-1',left,right)
while left < right - 1 and nums[right] == nums[right + 1]:
#print(' ri -1')
right -= 1
sum_new = nums[element1] + nums[element2] + nums[left] + nums[right]
# 同样的，特殊情况就是留给left的一个值他并没有使用，而是继续自己使用的情况，那就是重复值
if left == right - 1 and nums[right] == nums[right - 1] and (sum == target or sum_new < target):
#print('le == ri -1')
break
while element2 < left and nums[element2] == nums[element2 + 1]:
#print('ele2', element2)
element2 += 1
f2 += 1
while element1 < len_nums - 3 and nums[element1] == nums[element1 + 1]:
#print('ele1', element1)
element1 += 1
f1 += 1
return result_ls运行结果：
分析：
四数之和，和15.三数之和是一个思路，都是使用双指针法, 基本解法就是在15.三数之和 的基础上再套一层for循环。
但是有一些细节需要注意，例如： 不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。（大家亲自写代码就能感受出来）
15.三数之和的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下表作为双指针，找到nums[i] + nums[left] + nums[right] == 0。
四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下表作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3) 。
那么一样的道理，五数之和、六数之和等等都采用这种解法。
对于15.三数之和双指针法就是将原本暴力O(n^3)的解法，降为O(n^2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。
之前我们讲过哈希表的经典题目：454.四数相加II，相对于本题简单很多，因为本题是要求在一个集合中找出四个数相加等于target，同时四元组不能重复。
而454.四数相加II是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于本题还是简单了不少！
我们来回顾一下，几道题目使用了双指针法。
双指针法将时间复杂度O(n^2)的解法优化为 O(n)的解法。也就是降一个数量级，题目如下：
操作链表：
双指针法在字符串题目中还有很多应用，后面还会介绍到。
参考代码：
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
for i in range(n):
if i > 0 and nums[i] == nums[i - 1]: continue
for k in range(i+1, n):
if k > i + 1 and nums[k] == nums[k-1]: continue
p = k + 1
q = n - 1
while p < q:
if nums[i] + nums[k] + nums[p] + nums[q] > target: q -= 1
elif nums[i] + nums[k] + nums[p] + nums[q] < target: p += 1
else:
res.append([nums[i], nums[k], nums[p], nums[q]])
while p < q and nums[p] == nums[p + 1]: p += 1
while p < q and nums[q] == nums[q - 1]: q -= 1
p += 1
q -= 1
return res运行结果：
总结：
其实代码逻辑差别不大，但是明显参考答案更简洁，我可能存在下面一些原因：
1.对于双指针方法不够熟练
2.逻辑混乱导致觉着很复杂
但是通过调试的过程中加深了对双指针的理解，失败是成功之母!