LeetCode 01 两数之和

题目

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

注意

1.同样的元素不能重复使用(也就是不能自己加自己)

2.给定的数组中可能有相同的元素(比如 [3, 3, 4, 4, 5])

方法一

思路:通过暴力搜索求解,遍历nums列表中所有的两个元素之和nums[i]和nums[j],时间复杂度为O(n^2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from typing import List

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(len(nums)):
if nums[i] + nums[j] == target:
return [i, j]

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(len(nums)):
if j > i:
if nums[i] + nums[j] == target:
return [i, j]

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(len(nums)-(i+1)):
j = j + (i+1)
if nums[i] + nums[j] == target:
return [i, j]

class Solution:
def twoSum(self, nums: List[int], target: int) -> 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]

写这种方法的时候,在第二个for循环时遇到了问题根据注意点1,同样的元素不能重复使用,因此第一次尝试,当输入为[3,2,4]和6时,返回的[0,0]错误,正确应为[1,2],原因就是同样的元素被重复使用了,最终导致解答错误。第二次尝试,试图不重复利用,加入了判断if j > i,由于浪费了很多步骤导致了超时。第三次尝试,遵循元素不重复使用的原则,第二个for循环我们要找的下标开始数值不是0,而是与i有关,从i+1开始,而且第二个for循环每次的循环次数是变化的,因此加入了for j in range(len(nums)-(i+1)):和j = j + (i+1)分别控制循环次数和开始数值,但是依然超时了。当时可能是脑子坏掉了,忘记了range(i+1, len(nums))这种定义for循环开始数值和循环次数的方式,第四次尝试,通过range(i+1, len(nums))同时解决了循环次数和开始数值的问题。

方法二

思路:先生成一个下标的列表a,一个一个取出nums中的元素,计算target与取出的元素的差c,将nums与下标的列表a一一对应构成字典b,删除字典b中取出的元素nums[i],查看差c是否在删除元素后的字典b中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from typing import List

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
a = range(len(nums))
for i in range(len(nums)):
c = target - nums[i]
b = dict(zip(nums, a))
del b[nums[i]]
if c in b:
return [i, b[c]]

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
a = range(len(nums))
for i in range(len(nums)):
c = target - nums[i]
b = dict(zip(a, nums))
del b[a[i]]
if c in b.values():
return [i, list(b.keys())[list(b.values()).index(c)]]

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
a = range(len(nums))
b = dict(zip(a, nums))
for i in range(len(nums)):
c = target - nums[i]
n = b
del n[a[i]]
if c in n.values():
return [i, list(n.keys())[list(n.values()).index(c)]]

写这种方法的时候,第一次尝试出现的问题是,根据注意点2,如果给定的数组中有相同的元素,而字典中的键是不能重复的,所以当输入[3,3]和6时,构成的字典b是{3: 1},而不是{3: 0, 3: 1},导致计算错误。想出的解决办法是,构成字典时,让nums充当值,让下标的列表a充当键,因为下标的列表是不可能重复的,这样就解决了上述问题,但是新的问题就来了,如何判断target与取出的元素的差c是否在删除元素后的字典b的值中并找到其对应的键?第二次尝试,通过list(b.values())和list(b.keys())再将字典拆成两个列表,分别是值和键,通过if c in b.values():判断c是否在b中,然后通过list(b.values()).index(c)定位c的下标,再通过list(b.keys())[]找到c对应的键,但是很遗憾,又超时了。分析原因可能是因为每一次循环都要重新构成字典b导致超时,第三次尝试,在for循环前构成字典b,每一次for循环定义一个新的字典n,将b赋给n,后面都是用n来进行操作,这样省去了每次循环构成字典b的运算步骤,最终运行通过。

方法三

使用哈希的思想,利用Python中list的查询方式,将复杂度降低到O(n)。

一个一个取出nums中的元素nums[i],计算target与nums[i]的差b,将nums[i]后面的元素构成新的列表c,判断差b是否在列表c中,如果在,返回下标c.index(b) + i + 1。此处运行通过,但时间相对方法二并没有缩短。

1
2
3
4
5
6
7
8
9
10
11
from typing import List

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
i = 0
while i < len(nums):
b = target - nums[i]
c = nums[i+1:]
if b in c:
return [i, c.index(b) + i + 1]
i = i + 1

方法四

先定义一个空字典d,一个一个取出nums中的元素,其下标为i,元素的值为m,计算target与m的差n,如果n在d中,则返回下标,如果不在,则将m加入到字典中。这样,直到target与我们取出的元素的差在字典中时,就完成了任务。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from typing import List

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
d = {}
for i, m in enumerate(nums):
n = target - m
if n in d:
return [d[n], i] # 此处顺序不能颠倒,d[n]在前,i在后,因为先加入字典d中的,是下标较小的,i对应的是后取出的,下标是较大的。
else:
d[m] = i

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
d = {}
for i, m in enumerate(nums):
n = target - m
if n in d.values():
return [list(d.keys())[list(d.values()).index(n)], i]
else:
d[i] = m

这种方法同样存在一个问题,由于字典中的键是不能重复的,如果像上面这样写,d[m] = i,则又是将元素m作为了键,下标作为了对应的值,一旦出现数组中有相同的元素的情况,就会导致计算错误或计算结果与其他方法不一致。如nums = [3, 3, 4, 4, 5]和target = 9时。受方法二时的影响,我们将下标作为键,元素m作为与下标对应的值,通过if n in d.values():判断n是否在d中,然后通过list(d.values()).index(n)定位n的下标,再通过list(d.keys())[]找到n对应的键。

测试

1
2
3
4
5
nums = [3, 3, 4, 4, 5]
target = 9
c = Solution()
x = c.twoSum(nums, target)
print (x)

注:此题的代码均未考虑无解的情况。


End~~~
0%