【算法】4Sum 四数之和

**四数之和（4Sum）**

在计算机科学中，四数之和是一道经典的算法题目。给定一个整数数组和一个目标值，我们需要找到其中四个数字的组合，使得它们的总和等于目标值。

**问题描述**

假设我们有一个长度为 `n` 的整数数组 `nums`，以及一个整数 `target`。我们的任务是找出其中四个数字的组合，使得它们的总和等于 `target`。

**示例**

例如，如果 `nums = [1,0, -1,0, -2,2]` 和 `target =0`，那么我们应该返回 `[[-2, -1,1,2], [-2,0,0,2]]`。

**解决方案**

这个问题可以使用双指针和哈希表来解决。具体来说，我们可以先将数组排序，然后使用两个指针分别从两端向中间移动，直到找到满足条件的四个数字。

**算法步骤**

1. 首先，将数组 `nums` 排序。
2. 初始化两个指针 `i` 和 `j` 分别指向数组的开始和结束。
3. 初始化一个哈希表 `hash` 来存储已经找到的组合。
4. 遍历数组，直到 `i` 小于 `n-3` 或 `j` 大于2 为止。
5. 对于每个 `i` 和 `j`，使用两个指针 `k` 和 `l` 分别从 `nums[i+1]` 和 `nums[j-1]` 开始向中间移动。
6. 当 `k` 小于 `n-1`且 `l` 大于0 时，检查是否存在一个组合使得 `nums[k] + nums[l] = target - nums[i] - nums[j]`。
7. 如果找到这样的组合，则将其添加到哈希表中并返回。
8. 最终，如果没有找到满足条件的组合，则返回空列表。

**代码示例**

def fourSum(nums, target):
 """
 Returns all unique quadruplets in the given array that sum up to the target value.

 Args:
 nums (list): A list of integers.
 target (int): The target sum.

 Returns:
 list: A list of lists, where each sublist is a quadruplet that sums up to the target value.
 """
 # Sort the input array nums.sort()

 result = []
 for i in range(len(nums) -3):
 if i >0 and nums[i] == nums[i-1]:
 continue for j in range(i +1, len(nums) -2):
 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` 排序，以便于后续的双指针和哈希表操作。
* 初始化两个指针 `i` 和 `j` 分别指向数组的开始和结束，用于遍历数组。
* 使用两个指针 `k` 和 `l` 分别从 `nums[i+1]` 和 `nums[j-1]` 开始向中间移动，以检查是否存在一个组合使得 `nums[k] + nums[l] = target - nums[i] - nums[j]`。
* 当找到这样的组合时，将其添加到哈希表中并返回。
* 最终，如果没有找到满足条件的组合，则返回空列表。

**时间复杂度**

该算法的时间复杂度为 O(n^3)，其中 n 是输入数组的长度。具体来说，遍历数组的过程需要 O(n) 的时间，而对于每个 i 和 j，我们使用两个指针 k 和 l 分别从 nums[i+1] 和 nums[j-1] 开始向中间移动，这也需要 O(n) 的时间。

**空间复杂度**

该算法的空间复杂度为 O(n)，因为我们使用一个哈希表来存储已经找到的组合。