Skip to content

1 两数之和

约 356 个字 15 行代码 预计阅读时间 2 分钟

力扣1 两数之和

Python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

示例 1：

Python
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
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]

逐字详解：首先输入的数组是nums，假设nums = [2,7,11,15]，i=0,1,2,3 当 i=0时，此时target=9，target-nums[0]=9-2=7,7不在字典中，因为字典是空的，所以执行dict[num[i]] = i 即 dict[nums[0]]=0 ，dict[2]=0，i=1,target-nums[i]=9-nums[1]=9-7=2,2在字典中，所以执行else return[dict[2],1]=[0,1]返回，得到结果

再来：首先定义空字典，用来存储已经遍历过的数字及其对应的索引；接下来 for loop遍历数组nums,其中i是当前遍历到的数字的索引；如果不在字典中，说明之前没有遇到过与当前数字相加等于target的数字，因此将当前数字及其索引存入字典中。如果在字典中，说明已经找到了一对数字，和等于target，于是返回这两个数字的索引。这两个索引分别是dict[target-nums[i]]（存储差值 对应的索引）和 i（当前数字的索引）

分析时间复杂度为O(n)，其中n为数组的长度，因为每个元素只被访问一次，空间复杂度为O(n)，最坏的情况是可能需要存储所有元素的索引

这个方法使用了哈希表（通过字典）快速查找目标数字，是一种典型的哈希表应用场景，提高查找效率

add_circle2024-11-14 16:25:48update2024-11-25 10:45:52