Python解LeetCode第1题：两数之和

在这个LeetCode题目中，我们讨论的是寻找一个给定数组`nums`中的两个数，它们的和等于目标值`target`，并且每个数仅被使用一次。这个问题可以通过不同的算法策略来解决，重点在于优化时间和空间复杂度。 首先，我们介绍一种暴力求解方法。这种方法通过两层循环实现，外部循环遍历数组中的每个元素`nums[i]`，内部循环则检查剩余数组（即从`nums[i+1:]`开始）中是否存在`target - nums[i]`。这个方法虽然直观，但时间复杂度是O(n^2)，因为每次内部循环都需要在剩下的数组中查找，导致效率低下。代码实现如所示： ```python class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in nums: j = target - i start_index = nums.index(i) next_index = start_index + 1 temp_nums = nums[next_index:] if j in temp_nums: return (start_index, next_index + temp_nums.index(j)) ``` 然而，这种暴力搜索方法并不适用于大规模数据，因为它的时间复杂度过高。为了提高效率，我们可以使用哈希表（字典）来存储已经遍历过的数及其索引。当我们在遍历过程中遇到一个数`nums[i]`时，我们可以检查`target - nums[i]`是否已经在字典中，如果存在，说明找到了一对满足条件的数，直接返回它们的索引；如果不存在，就将当前的`nums[i]`和其索引`i`加入字典。这样，查找时间复杂度降低到了O(1)，总的时间复杂度为O(n)。以下是优化后的解决方案： ```python class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: dict = {} for i in range(len(nums)): if target - nums[i] not in dict: dict[nums[i]] = i else: return [dict[target - nums[i]], i] ``` 通过使用字典，这个版本的解决方案显著提高了算法性能，使其在处理大型数据集时更具效率。对于那些寻求高效解法的面试者或开发者来说，理解并应用这种数据结构优化技巧是职场和职业发展中的重要技能。