LeetCode刷题笔记：实现数组两数之和算法

资源摘要信息:"LeetCode刷题笔记——添加元素使和等于目标值" 在LeetCode上，存在一类题目是要求通过增加数组中的元素来使得数组元素的总和等于给定的目标值。这类问题考察的是对数组的基本操作以及算法思维的运用。本篇笔记将详细解析如何在遇到这类问题时如何进行思考和解决。 1. 题目解析 在题目中，我们通常会给出一个数组`nums`和一个目标值`target`。我们需要找到数组中两个数，使得它们的和等于目标值。这里需要注意的是，数组中的每个元素只能使用一次，并且需要返回它们的索引。 例如，给定数组`nums = [2, 7, 11, 15]`和目标值`target = 9`，我们可以通过返回索引`[0, 1]`来满足条件，因为`nums[0] + nums[1] = 2 + 7 = 9`。 2. 算法思路 解题之前需要考虑各种可能的情况，尤其是数组的特殊情况，比如空数组`[]`、只有一个元素的数组`[1]`、包含重复元素的数组`[3,3]`以及常规情况`[1,2,3,4,3]`等。 一种通用的解题方法是使用哈希表（在Python中可以使用`defaultdict`）来存储已经遍历过的数字及其索引。遍历数组的同时，对于每个元素`i`，计算`target - i`的值，然后查看这个差值是否已经在哈希表中。如果存在，就找到了一对和为`target`的数字。返回当前数字`i`的索引和哈希表中存储的差值的索引即可。 3. 示例代码 示例代码中展示了如何使用`defaultdict`来实现上述算法思路： ```python from collections import defaultdict cc = [1, 2, 3, 2, 4] dd = defaultdict(list) for i, v in enumerate(cc): dd[v].append(i) print(dd) ``` 接下来是针对具体问题的`twoSum`函数实现： ```python def twoSum(self, nums, target): res = [] for index, i in enumerate(nums): # 使用enumerate同时获取索引和值 temp = [] b = target - i if b in nums[index + 1:]: temp.append(index) temp.extend([nums.index(b, index + 1), nums.index(b, index + 1) + 1]) res.append(temp) return res ``` 上述代码中使用了`enumerate`来遍历数组，并且用一个临时列表`temp`来存储结果。通过`if b in nums[index + 1:]`判断是否存在符合条件的数字，并且使用`list.index`方法来查找数字`b`的索引。这种方法的时间复杂度较高，因为它在剩余数组中使用线性搜索查找目标值。 为了避免使用低效的搜索，我们可以利用一个哈希表来存储已经遍历过的数字，从而将查找时间复杂度降低到O(1)。 4. 更优解法 更优的解法如下，使用哈希表来降低查找时间复杂度： ```python def twoSum(self, nums, target): prev_map = {} # val -> index for i, num in enumerate(nums): diff = target - num if diff in prev_map: return [prev_map[diff], i] prev_map[num] = i return [] ``` 此方法通过构建一个从数字到索引的映射（即哈希表），在遍历数组的同时存储每个数字的索引。对于每个元素，计算出目标值和当前元素的差值，然后直接从哈希表中查找这个差值是否已经存在，如果存在，则返回当前索引和哈希表中存储的索引。 5. 小结 LeetCode上的这类添加元素使和等于目标值的题目，是考察数组处理和基本算法思维的入门级问题。通过构建哈希表的方法可以有效降低时间复杂度，提高算法效率。掌握此类题目的解法，对刷题进阶之路至关重要。 【标签】:"系统开源"，这可能意味着解题方法或代码实现可以采用开源的原则和实践，例如遵循代码的清晰性、可读性以及良好的注释习惯，这样他人可以更容易地理解和复用。 【压缩包子文件的文件名称列表】: DailyAlgorithm-master，从文件名可以推测这是一个包含每日算法练习或总结的项目或文件夹。"DailyAlgorithm"暗示了对算法每日练习或学习的习惯，而"master"则可能表示这是主版本或者主分支，包含了练习的核心代码和笔记。