超琐碎 ≈ 完整记录 + 深入探究 + 任性吐槽
问题地址,难度:Easy,标签:Array | Hash Table
若有错误之处请予以指正:)
问题描述
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.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
题意分析
- 同一个数最多用一次:Given nums =
[1]
, target =2
-> return[0, 0]
错误输出 - 列表中可能含负整数:Given nums =
[-3, -1, 11, 3]
, target =-4
-> return[0, 1]
- 列表中可能有相等数字:Given nums =
[3, 7, 11, 3]
, target =6
-> return[0, 3]
- 唯一解:不会出现这样一些case:
- Given nums =
[3, 1, 11, x, x, x, ..., x, 3]
, target =4
- Given nums =
[3, 2, x, x, x, ..., x, 1, 4]
, target =5
- Given nums =
- 返回顺序无限制:Given nums =
[2, 7, 11, 15]
, target =9
-> return[1, 0]
or[0, 1]
我的实现及调优过程
方法1:3460 ms
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
i = 0
while(i<len(nums)-1):
a = nums[i]
for b in nums[i+1:]:
if target - a == b:
return [i, nums[i+1:].index(b)+i+1]
i += 1
暴力解法,两层循环。
- 时间复杂度:O(n^2)
- 空间复杂度:O(1)
方法2:3189 ms
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
i = 0
while(i<len(nums)-1):
a = nums[i]
nums_ = nums[i+1:]
for b in nums_:
if target - a == b:
return [i, nums_.index(b)+i+1]
i += 1
小改动,减少了切片的冗余使用。
- 时间复杂度:O(n^2)
- 空间复杂度:O(1)
方法3:1197 ms
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
i = 0
while(i<len(nums)-1):
a = nums[i]
nums_ = nums[i+1:]
if target - a not in nums_:
i += 1
continue
for b in nums_:
if target - a == b:
return [i, nums_.index(b)+i+1]
在第一层循环中,首先使用in
检查(target-a)
这个值是否在剩下的数组nums_
里,如果在,才进入下一层循环从nums_
找到(target-a)
值的位置,省了逐个进行target - a == b
的计算时间。
- 时间复杂度:O(n^2)
- 空间复杂度:O(1)
方法4:1228 ms
from collections import defaultdict
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
value2index = defaultdict(list)
for i, e in enumerate(nums):
value2index[e].append(i)
i = 0
while(i < len(nums)-1):
a = nums[i]
nums_ = nums[i+1:]
if target - a not in nums_:
i += 1
continue
for b_index in value2index[target-a]:
if b_index != i:
return [i, b_index]
使用defaultdict(list)
命名为value2index
,首先循环遍历列表nums
,将每个数的值与其位置记录在value2index
中,值作为key,位置放入value(list);接下来再循环一遍列表nums
,找出target-a
的值并在value2index
里查出其在nums
的位置,如果位置与a不同,输出;否则继续。省了逐个进行target - a == b
的计算时间。
- 时间复杂度:O(2n) ~ O(n) (虽然有两层循环,但第二层有唯一解作为bound)
- 空间复杂度:O(n)
方法5:44 ms
from collections import defaultdict
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
value2index = defaultdict(list)
for a_index, a in enumerate(nums):
value2index[a].append(a_index)
for b_index in value2index[target-a]:
if b_index != a_index:
return [a_index, b_index]
这一次有飞跃式的进步,仍然使用defaultdict(list)
作为value2index
,但是value2index
中每次加入nums
里的值a
后,紧跟着去查value2index
有没有成功与该值配对的target-a
值,这样nums
只会被循环遍历一次。
- 时间复杂度O(n)
- 空间复杂度O(n)
方法6:38 ms
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
value2index = dict()
for a_index, a in enumerate(nums):
b_index = value2index.get(target-a, None)
if b_index not in (None, a_index):
return [a_index, b_index]
value2index[a] = a_index
细想之下,之前之所以用defaultdict(list)
,而不是dict
作为value2index
,是担心nums
中如果有相同的值a1和a2时,在a2加入value2index
时a1会被覆盖掉,但是这会不会影响算法的正确性呢?考虑下面几种特殊情况,似乎并不会有问题:
- a等于
target-a
- Given nums =
[3, 1, 2, 3]
, target =6
(只要第二个3
在加入dict
前做查询,第一个3
就不会被覆盖,OK) - Given nums =
[3, 1, 2, 3, 3]
, target =6
(由于唯一解的限制,这种情况不存在) - Given nums =
[3, 1, 2, 2, 3]
, target =6
(2
被覆盖,但无所谓,OK) - Given nums =
[3, 1, 2, 4]
, target =6
(2
被覆盖,但无所谓,OK)
- Given nums =
- a不等于
target-a
- Given nums =
[3, 4, 2, 1]
, target =4
(OK) - Given nums =
[2, 2, 3, 4]
, target =5
(唯一解限制,情况不存在)
- Given nums =
- 两组解,一组a等于
target-a
,一组a不等于target-a
(唯一解限制,情况不存在)- Given nums =
[3, 1, 2, 4]
, target =6
- Given nums =
方法6
等同于Leetcode网站上的Solutions(JAVA)里提到的最优方法,不过这种方法固然是快,但思路不够自然,要考虑一堆犄角旮旯的case,现实里测试总是难保证覆盖全所有情况。从实践角度上来讲,使用的假设强度和性能需要有个平衡,因此我觉得方法5
相对更好。
- 时间复杂度O(n)
- 空间复杂度O(n)
网友评论