LeetCode—1. 两数之和—python

题目详情

题目链接: https://leetcode.cn/problems/two-sum/
1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

思维总结

1. 嵌套两层for列表，找出两数之和等于target；不如用“被减数=target-减数”，遍历减数，在再检验被减数是否存在于列表中。
2. 第二层for不必要查找整个列表，从当前数字位置之前或之后查找即可。
3. 巧妙运用字典。

学习要点

1. enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中；
   enumerate(sequence, [start=0])，sequence – 一个序列、迭代器或其他支持迭代对象。start – 下标起始位置。
   
2. Python 字典 get() 函数返回指定键的值；
   dict.get(key[, value]) ，key – 字典中要查找的键。value – 可选，如果指定键的值不存在时，返回该默认值。返回指定键的值，如果键不在字典中返回默认值 None 或者设置的默认值；
   get(key) 方法在 key（键）不在字典中时，可以返回默认值 None 或者设置的默认值。dict[key] 在 key（键）不在字典中时，会触发 KeyError 异常。
   
3. 字典中，key到value是指针映射，不是值映射。

更优解答

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}    # 建立一个字典记录记录索引和值的对应关系
        for i, num in enumerate(nums):  # enumerate()函数列出nums列表中数据的下标和数据
            # num 是其中一个加数， target-num 对应另一个被加数
            # 在字典中搜索 target-num 是否存在
            # 如果，存在则证明找出了列表中两个数相加等于目标值，返回这两个数据的下标
            # 否则，把这对数据的下标和数据存入字典中
            if hashmap.get(target - num) is not None:
                return [i, hashmap.get(target - num)]
            # 把当前的数据下标和数据以键值对的形式存入字典中
            # 将 hashmap[num] = i 放在 if 之后，
            # 可以解决列表中有两个元素的值是相同的，或者target-num=num的情况
            hashmap[num] = i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我的解答

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []  # 存放结果的列表
        fla = 0  # 跳出第一层循环的标识
        # 为了遍历列表的所有值
        for i in range(len(nums)):
            # 为了遍历位于当前值之后的所有值
            for j in range(1, len(nums) - i):
                # 如果当前值加上后面的某一个值等于目标值
                if nums[i] + nums[i + j] == target:
                    # 则将符合条件的数值的索引分别加入结果列表中
                    # 并改变跳出循环的标识符
                    # 并跳出当前的内层循环
                    result.append(i)
                    result.append(i + j)
                    fla = 1
                    break
            # 如果标识符改变，说明已经找到结果了，跳出外层循环
            if fla == 1:
                break
        return result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22