给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/4sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
nums = [1,-2,-5,-4,-3,3,3,5] target = -11 rs = [] # 对数列进行递增排序 nums.sort() # nums = [-5,-4,-3,1,3,3,3,5] # print(nums) # 设置最小的第一个 指针 k for k in range(len(nums) - 2): # 设置l,r指针 r = len(nums) - 1 # 指向最大 K 变化一次再次指向最后 l = k + 1 # 不断指向下一个变换的 mid = l + 1 # 不断指向下一个变换的中间指针 # 最小的指针指向大于1 与指向相同的结果时跳过 # print('k: %d,l: %d,mid: %d,r: %d' % (k, l, mid, r)) # print('nums[k]: %d,nums[l]: %d,nums[mid]: %d,nums[r]: %d' % (nums[k], nums[l], nums[mid], nums[r])) if target >= 0 and (nums[k] > target): # -5 > -11 break if (k > 0) and (nums[k] == nums[k - 1]): continue for l in range(k + 1, r): # print('k: %d,l: %d,mid: %d,r: %d' % (k, l, mid, r)) # print('nums[k]: %d,nums[l]: %d,nums[mid]: %d,nums[r]: %d' % (nums[k], nums[l], nums[mid], nums[r])) # 重置 r , mid 指针 r = len(nums) - 1 mid = l + 1 # 处理相同的指针元素 l,r if (l > k + 1) and (nums[l] == nums[l - 1]): continue if (r < len(nums) - 1) and (nums[r] == nums[r + 1]): r -= 1 continue # 判断mid指针 while l <= mid < r: # 去重 （处理相同的指针元素） 跳过本次循环进行下一轮循环 if (mid > l + 1) and (nums[mid] == nums[mid - 1]): mid += 1 continue s = nums[k] + nums[l] + nums[mid] + nums[r] # print(s) # s == 0 说明结果符合 将索引指向元素记录 if s == target: # targent = 0 rs.append([nums[k], nums[l], nums[mid], nums[r]]) mid += 1 r -= 1 # s < 0 的情况 说明 l 指针需要向后移一位 elif s < target: mid += 1 # s>0 的情况说明 r 指针需要往前移一位 else: r -= 1 print(rs)双指针法嵌套了三个循环O（n**3）复杂度过高 一下为另一种方法：
nums = [1, 0, -1, 0, -2, 2] nums.sort() output = [] target = 0 def Search(i, target, oneSolution): if target == 0 and len(oneSolution) == 4: # 出口，找到正确的解了 output.append(oneSolution) return elif len(oneSolution) > 4 or i >= len(nums): # 剪枝，超范围了 return if target - nums[i] - (3 - len(oneSolution)) * nums[-1] > 0 or nums[i] in notSelected: # 当前这个数太小了 target 减去nums[i](指定位置的元素) 加上 剩余座位（最大的元素）依然大于0 # 说明当前位置元素太小了 # 应寻找下一个 i+ 1 Search(i + 1, target, oneSolution) elif target - (4 - len(oneSolution)) * nums[i] < 0: # 当前组数的和太大了 直接返回 return else: # 当前组数似乎没毛病 Search(i + 1, target, oneSolution,notSelect+nums[i]) # 不选这个数 Search(i + 1, target - nums[i], oneSolution + [nums[i]],notSelected) # 选这个数 Search(0, target, [],[]) print(output)