力扣热门100题之三数之和【中等】

**力扣热门100题之三数之和**

**题目描述**

给定一个大小为 `n` 的整数数组 `nums` 和一个目标整数 `targetSum`，找出三个数字的组合，使得它们的和等于 `targetSum`。返回所有可能的组合。

**示例1**

输入：`nums = [1,2,3,6]`, `targetSum =6`

输出：`[[1,2,3]]`

**示例2**

输入：`nums = [1,1,1,1,1], targetSum =3`

输出：`[[1,1,1]]`

**示例3**

输入：`nums = [1,2,3,4,5,6], targetSum =7`

输出：`[[1,2,4],[1,3,3],[2,2,3]]`

**解决方案**

我们可以使用回溯法来解决这个问题。回溯法是一种递归的方法，用于遍历所有可能的组合。

def threeSum(nums):
 """
 给定一个大小为 n 的整数数组 nums 和一个目标整数 targetSum，
 找出三个数字的组合，使得它们的和等于 targetSum。
 Args:
 nums (list):一个大小为 n 的整数数组 targetSum (int): 目标整数 Returns:
 list: 所有可能的组合 """
 n = len(nums)
 if n < 3:
 return []
 # 首先对数组进行排序 nums.sort()
 result = []
 for i in range(n -2):
 # 如果当前数字与前一个数字相同，跳过当前循环 if i >0 and nums[i] == nums[i -1]:
 continue left, right = i +1, n -1 while left < right:
 total = nums[i] + nums[left] + nums[right]
 if total < targetSum:
 left +=1 elif total > targetSum:
 right -=1 else:
 # 如果找到一个组合，添加到结果中，并跳过当前循环 result.append([nums[i], 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 = [1,2,3,6]
targetSum =6print(threeSum(nums)) # 输出: [[1,2,3]]

nums = [1,1,1,1,1]
targetSum =3print(threeSum(nums)) # 输出: [[1,1,1]]

nums = [1,2,3,4,5,6]
targetSum =7print(threeSum(nums)) # 输出: [[1,2,4], [1,3,3], [2,2,3]]

**注释**

* 我们首先对数组进行排序，这样我们可以使用双指针法来找到三个数字的组合。
* 我们使用回溯法来遍历所有可能的组合。每次循环中，我们都会尝试将当前数字与其他两个数字相加，如果总和等于目标整数，我们就会添加这个组合到结果中。
* 如果找到一个组合，我们会跳过重复的组合，以避免添加多余的组合。

**时间复杂度**

* 时间复杂度为 O(n^2)，其中 n 是数组的大小。我们使用双指针法来遍历所有可能的组合，每次循环中，我们都会尝试将当前数字与其他两个数字相加。
* 空间复杂度为 O(n)，其中 n 是数组的大小。我们需要存储所有可能的组合。

**总结**

* 我们使用回溯法来解决这个问题，首先对数组进行排序，然后使用双指针法来找到三个数字的组合。
* 如果找到一个组合，我们会添加到结果中，并跳过重复的组合，以避免添加多余的组合。
* 时间复杂度为 O(n^2)，空间复杂度为 O(n)。