【优选算法题练习】day7

**优选算法题练习 Day7**

### 题目描述在一个有序的整数列表中，找出两个数字之和等于给定目标值的所有可能组合。

#### 示例：

* 输入：nums = [2,7,11,15], target =9* 输出：[[2,7]]
* 解释：因为 [2,7] 和 [7,2] 都是两个数字之和为9 的组合，我们返回的解集仅包含 [2,7]。

### 题目要求* 给定一个有序整数列表 `nums` 和一个目标值 `target`
* 找出所有可能的组合，使得两个数字之和等于 `target`
* 返回的解集中，不包含重复的组合* 如果没有这样的组合，则返回空列表### 解决方案#### 方法1：暴力破解法（不推荐）

def twoSum(nums, target):
 # 暴力破解法，时间复杂度为 O(n^2)
 result = []
 for i in range(len(nums)):
 for j in range(i +1, len(nums)):
 if nums[i] + nums[j] == target:
 result.append([nums[i], nums[j]])
 return result

#### 方法2：哈希表法（推荐）

def twoSum(nums, target):
 # 哈希表法，时间复杂度为 O(n)
 num_dict = {}
 result = []
 for i in range(len(nums)):
 complement = target - nums[i]
 if complement in num_dict:
 result.append([complement, nums[i]])
 num_dict[nums[i]] = i return result

###代码注释* 在方法1 中，我们使用了暴力破解法，遍历列表中的每个数字，并检查与其他数字的和是否等于目标值。如果找到这样的组合，则添加到结果中。
* 在方法2 中，我们使用了哈希表法。我们先创建一个空字典 `num_dict` 来存储列表中的数字及其索引。然后，我们遍历列表中的每个数字，并检查其补数（即目标值减去该数字）是否已经存在于字典中。如果找到这样的组合，则添加到结果中。
* 在两种方法中，我们都返回了一个包含所有可能组合的列表。

### 时间复杂度* 方法1 的时间复杂度为 O(n^2)，因为我们需要遍历列表中的每个数字，并检查与其他数字的和是否等于目标值。
* 方法2 的时间复杂度为 O(n)，因为我们只需遍历列表中的每个数字一次，并检查其补数是否已经存在于字典中。

### 空间复杂度* 方法1 需要额外的空间来存储结果列表，空间复杂度为 O(n)。
* 方法2 需要额外的空间来存储字典 `num_dict`，空间复杂度为 O(n)。

### 最终答案最终答案是使用哈希表法（方法2），因为它具有更好的时间和空间效率。