nums = [3, 2, 4]
1. 暴力解法
class Solution:
def twoSum(self, nums, target=int):
for i in range(len(nums)):
res = target - nums[i]
for j in range(i + 1, len(nums)):
if res == nums[j]:
return [i, j]
- 这种方法最直观明了,这样也往往意味着高时间复杂度,此时的时间复杂度为 O(n2)
2. 使用字典
class Solution2:
def twoSum(self, nums, target=int):
hashmap = {}
for i, v in enumerate(nums):
hashmap[v] = i
for i, v in enumerate(nums):
j = hashmap.get(target - v)
if j and i != j:
return [i, j]
- python中的dict数据类型,采用的就是哈希表实现的,此时时间复杂度为 O(n) + O(n)即 O(n)。
- 仔细观察,方法2我们很容易发现,使用了两次for循环,而且for循环的作用很单一,这就让我们联想到能不能减少一次for循环呢?
- 以下就是进一步优化后的代码。
3. 进一步优化
class Solution3:
def twoSum(self, nums, target):
hashmap = {}
for i, num in enumerate(nums):
if hashmap.get(target - num) is not None:
return [i, hashmap.get(target - num)]
hashmap[num] = i
- 方法3只是在方法2的基础上减少了一次for循环,相当于之前的 2O(n2)的时间复杂度的常数去掉了,优化程度是有限的。
- 此时相较于方法1,时间复杂度的优化无疑是质的提升。