【算法与数据结构】18、LeetCode四数之和

题目描述：

给定一个包含 n个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

示例：

输入：nums = [1,0, -1,0, -2,2], target =0输出：[[-2, -1,1,2], [-2,0,0,2], [-1,0,0,1]]

解题思路：

1. 首先对数组进行排序，方便后续操作；
2. 使用四个指针分别指向四个元素，遍历数组，固定其中两个元素，然后使用双指针法找到另外两个元素；
3. 在遍历过程中，需要注意去重操作，避免重复的四元组；
4. 最终得到满足条件的四元组。

代码示例：

def fourSum(nums, target):
 nums.sort()
 res = []
 n = len(nums)
 for i in range(n-3):
 if i >0 and nums[i] == nums[i-1]:
 continue for j in range(i+1, n-2):
 if j > i+1 and nums[j] == nums[j-1]:
 continue left = j +1 right = n -1 while left < right:
 total = nums[i] + nums[j] + nums[left] + nums[right]
 if total == target:
 res.append([nums[i], nums[j], nums[left], nums[right]])
 while left < right and nums[left] == nums[left+1]:
 left +=1 while left < right and nums[right] == nums[right-1]:
 right -=1 left +=1 right -=1 elif total < target:
 left +=1 else:
 right -=1 return res# 测试nums = [1,0, -1,0, -2,2]
target =0print(fourSum(nums, target))