今天第一天开始刷leetcode,加油
题号:1
题目描述:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

例子:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

我的做法:无脑循环两次列表找到两个相加值等于需要找的值,简单暴力
时间复杂度:O(n^2)
空间复杂度:O(1)

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

运行的结果,实在太慢了,都至少4秒多。

再来看看大佬们的做法:
用一个字典保存数组中与目标相差的值,键就是这个相差的值,而值就是这个在数组中的位置。
当在字典中能存在这个与目标相差的值的时候即可有结果,就是可以把当前位置和之前那个相差值的坐标返回即可。
主要就是寻找与目标值相差得值即可。

时间复杂度: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]
"""
index_map = {}

for x in range(0, len(nums)):
if nums[x] in index_map:
return [index_map[nums[x]], x]
index_map[target-nums[x]] = x
return [-1, -1]

运行时间,只有64ms,我的与别人相差了一百倍差不多,有点远,哈哈。