Leetcode系列之两数之和
阅读原文时间:2022年02月22日阅读:1

Leetcode系列之两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
链接:https://leetcode-cn.com/problems/two-sum/

Python实现(三种方法)

class Solution(object):    @staticmethod    def two_sum_1(nums: list, target: int):        """方法一"""        for index1, num1 in enumerate(nums):            num2 = target - num1            if num2 in nums and nums.index(target - num1) != index1:                return [index1, nums.index(target - num1)]    @staticmethod    def two_sum_2(nums: list, target: int):        """方法二"""        num_dict = {}        for index, num in enumerate(nums):            num_dict[num] = index        for i, num in enumerate(nums):            j = num_dict.get(target - num)            if j and i != j:                return [i, j]    @staticmethod    def two_sum_3(nums: list, target: int):        """方法三"""        num_dict = {}        for index, num in enumerate(nums):            if target - num in num_dict:                return [num_dict[target - num], index]            num_dict[num] = index

go语言实现

package mainimport "fmt"func twoSum(nums []int, target int) []int {    maps := make(map[int]int) // map数据定义    nes := make([]int, 0)     // 切片数据定义    for key, val := range nums {        ant := target - val        _, st := maps[ant]        if st {            nes = append(nes, maps[ant]) // 切片添加            nes = append(nes, key)            return nes        }        maps[val] = key    }    return nes}func main() {    nums := []int{2, 7, 11, 15}    target := 9    ret := twoSum(nums, target)    fmt.Println(ret)}
  • 执行结果

方法

执行用时

内存消耗

语言

Python1

1168 ms

14.9 MB

Python3

Python2

68 ms

15.4 MB

Python3

Python3

68 ms

15 MB

Python3

go

4 ms

3.7 MB

Golang

从执行结果可以看到,go语言的执行速度最快,内存消耗最少,执行速度和内存消耗明显有自身的优势。而Python实现的三种方法中,方法一的时间复杂度为O(n2),列表循环时间复杂度为O(n),每一次循环内都会进行一次判断

 if num2 in nums and nums.index(target - num1) != index1:

in 列表查询的时间复杂度为O(n),因此整体时间复杂度为O(n2).方法二和方法三的时间复杂度为O(n),有人也许会说方法二和三的for循环中查询不是也要花费时间吗?我们带着问题去看一下方法二:

 """方法二"""        num_dict = {}        for index, num in enumerate(nums):            num_dict[num] = index        for i, num in enumerate(nums):            j = num_dict.get(target - num)            if j and i != j:                return [i, j]

两个for循环为O(n),字典赋值为O(1),字典查询为O(1)因此,整体时间复杂度为O(n)。

"""方法三"""        num_dict = {}        for index, num in enumerate(nums):            if target - num in num_dict:                return [num_dict[target - num], index]            num_dict[num] = index

方法三种in 字典时间复杂度为O(1),我们注意到这和方法一in 列表的O(n2)不同,字典查询确实比列表查询的效率高。

总结:不同语言之间的性能差异确实很大,尤其对于Python和go而言。go的性能确实无可挑剔,堪比C。但同时同一个题,同一种算法,python实现起来确实比较清爽,节省的时间、精力确实是python的优势,可以让人专注于程序的设计与思考,而不是各种复杂语法的实现。当然,不同语言各有优劣,社会需要什么,我们就去学什么,这才是王道!