python leetcode 1. 两数之和

 Pala   2018-09-17 19:44   52 人阅读  0 条评论

题目:

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

第一种解决方法(暴力解决):

def twoSum(self, nums, target):
	"""
	:type nums: List[int]
	:type target: int
	:rtype: List[int]
	"""

	for i, v in enumerate(nums):

		for l, k in enumerate(nums):
			if i == l:
				continue
			if k + v == target:
				return [i,l]

复杂度分析:

  • 时间复杂度:O(n^2)O(n 2 ), 对于每个元素,我们试图通过遍历数组的其余部分来寻找它所对应的目标元素,这将耗费 O(n)O(n) 的时间。因此时间复杂度为 O(n^2)O(n 2 )。

  • 空间复杂度:O(1)O(1)。 

第二种方法(hash值):

利用list的index() 和collections中defaultdict

def twoSum(self, nums, target):
	"""
	:type nums: List[int]
	:type target: int
	:rtype: List[int]
	"""
	from collections import defaultdict
	d = defaultdict(list)
	[d[v].append(i) for i, v in enumerate(nums)]

	for i, v in enumerate(nums):
		second_value = target - v
		try:
			index_li = d[second_value]
			for l in index_li:
				if i == l:
					continue
				return [i, l]
		except KeyError:
			continue	

复杂度分析:

  • 时间复杂度:O(n)O(n), 我们只遍历了包含有 nn 个元素的列表一次。在表中进行的每次查找只花费 O(1)O(1) 的时间。

  • 空间复杂度:O(n)O(n), 所需的额外空间取决于哈希表中存储的元素数量,该表最多需要存储 nn 个元素。


本文地址:http://chenxm.cc/post/710.html
版权声明:本文为原创文章,版权归 Pala 所有,欢迎分享本文,转载请保留出处!

发表评论


表情

还没有留言,还不快点抢沙发?