给定一个整数数组 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/
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
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)不同,字典查询确实比列表查询的效率高。
手机扫一扫
移动阅读更方便
你可能感兴趣的文章