— tags: “leetcode刷题记录” —

题目描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
来源：力扣（LeetCode）

参照官方文档实现, 刚学python，详细记录不会的点

方法一：暴力解题，双重循环
脑子里只有这一种方法。。

收获：1. list的长度函数len()
2. range()

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j]==target:
                    return i,j

执行用时：3184 ms 内存消耗：13.5 MB
时间复杂度O（n²） 空间复杂度O（1）

方法二：两遍哈希表
原来python的字典就是c++的map啊。。

收获：判断字典中含不含有某个键值用 if key in dict，has_key()在python3不能使用了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dict1={}
        for i in range(len(nums)):
            dict1[nums[i]]=i
        for i in range(len(nums)):
            c=target-nums[i]
            if c in dict1:
                if dict1[c]!=i:
                    return i,dict1[c]

执行用时：40 ms 内存消耗：14.1 MB
时间复杂度：O(n) 空间复杂度：O(n)

方法三：一遍哈希表
真巧妙啊！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        dict2={}
        for i in range(len(nums)):
            c=target-nums[i]
            if c in dict2:
                return dict2[c],i
            dict2[nums[i]]=i

执行用时：32 ms 内存消耗：14 MB
时间复杂度：O(n) 空间复杂度：O(n)

title: leetcode：两数之和 python实现
date: 2020-06-15 9:44:13
tags:

  • leetcode