LeetCode 1 两数之和 python

题目描述

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
样例

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

---

想法一： 两重循环，但是时间复杂度高
想法二： 遍历nums，得到每个target-nums[i]，然后在nums中找是否存在这个值，时间复杂度当然比一好，但不是最好

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        one=0
        success=False
        for i in nums:
            tag = target-i
            if tag in nums:
                two = nums.index(tag)
                if two!=one:
                    success = True
                    break
            one += 1
        if success is True:
            return one, two

想法三： 在查询资料后，得到了这种思想，遍历的时候，把该数的另一半放入字典，然后每次遍历的时候判断该数是否在字典中，即可完成该题

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 获取nums长度
        n = len(nums)
        # 创建索引字典
        d = {}
        # 遍历nums，每一次将与遍历数符合的数存入字典
        for i in range(n):
            # 得到符合的数
            sb = target - nums[i]
            if nums[i] in d.keys():
                # 如果存在，说明可以组成组合
                return d[nums[i]], i
            else:
                # 不存在，加入
                d[sb] = i

---

最后

刷过的LeetCode源码放在Github上了，希望喜欢或者觉得有用的朋友点个star或者follow。
有任何问题可以在下面评论或者通过私信或联系方式找我。
联系方式
QQ：791034063
Wechat：liuyuhang791034063
CSDN：https://blog.csdn.net/Sun_White_Boy
Github：https://github.com/liuyuhang791034063