【每日一题Day266】LC18四数之和 | 排序+双指针

**每日一题 Day266: LC18 四数之和**

**问题描述**

给定一个由整数组成的数组 `nums` 和一个目标整数 `target`，找出四个元素的组合，使得它们的和等于 `target`。你可以假设每种输入只有一种有效解。

**示例1:**

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

**示例2:**

* 输入：`nums = [0,0,0,0], target =0`
* 输出：`[[0,0,0,0]]`

**示例3:**

* 输入：`nums = [0,-2,1,0,-2,-2,3,2], target = -6`
* 输出：`[[-2,-2,-2,4],[-2,-2,0,6],[-1,-1,-2,6],[-1,0,-2,5],[-1,0,-1,6]]`

**解决方案**

我们可以使用排序和双指针的方法来解决这个问题。首先，我们对 `nums` 进行排序，然后我们使用两个指针，一个从头部开始（指向最小值），一个从尾部开始（指向最大值）。如果当前值之和等于目标值，我们就找到了一个解，并将其添加到结果列表中。如果当前值之和小于目标值，我们就移动左指针向右，如果当前值之和大于目标值，我们就移动右指针向左。

**代码示例**

class Solution:
 def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
 # 对nums进行排序 nums.sort()
 result = []
 for i in range(len(nums)):
 if i >0 and nums[i] == nums[i -1]:
 continue for j in range(i +1, len(nums)):
 if j > i +1 and nums[j] == nums[j -1]:
 continue left, right = j +1, len(nums) -1 while left < right:
 current_sum = nums[i] + nums[j] + nums[left] + nums[right]
 if current_sum < target:
 left +=1 elif current_sum > target:
 right -=1 else:
 result.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 return result

**注释**

* 我们首先对 `nums` 进行排序，这样我们就可以使用双指针的方法来找到四个元素的组合，使得它们的和等于 `target`。
* 我们使用两个循环，一个从头部开始（指向最小值），一个从尾部开始（指向最大值）。如果当前值之和等于目标值，我们就找到了一个解，并将其添加到结果列表中。如果当前值之和小于目标值，我们就移动左指针向右，如果当前值之和大于目标值，我们就移动右指针向左。
* 我们使用 `continue`语句来跳过重复的元素，这样我们就可以避免将相同的解添加到结果列表中多次。
* 最后，我们返回结果列表，包含所有满足条件的四元组。

**时间复杂度**

* 时间复杂度为 O(n^3)，其中 n 是 `nums` 的长度。这是因为我们使用了两个循环，每个循环都有 O(n) 个元素。
* 我们对 `nums` 进行排序，这样我们就可以使用双指针的方法来找到四个元素的组合，使得它们的和等于 `target`。

**空间复杂度**

* 空间复杂度为 O(n)，其中 n 是 `nums` 的长度。这是因为我们需要存储结果列表，包含所有满足条件的四元组。