需要以小于0 (n2)的复杂度重写代码

Question

我写了一个算法，给出了结果。给定一个由整数nums和整数target组成的数组，返回这两个数的下标，使它们之和等于target。

您可以假设每个输入只有一个解，并且您不能两次使用相同的元素。

你可以按任何顺序返回答案。

但是它太慢了，

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

if nums[j]==second_val:
res.append(i)
res.append(j)
return res
return res

有谁能帮我重写一下后续:你能想出一个时间复杂度小于O(n2)的算法吗?

Answer 1

在O(n)时间复杂度中，可以按以下代码完成。

逻辑为，由于给定输入中存在解对，即这些值的和构成目标，即val1 + val2 = target，因此我们需要遍历列表并搜索val2 = target - val1，如果找到则返回结果。

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
info = {}
for i, v in enumerate(nums):
if target-v not in info:
info[v] = i
else:
return [info[target-v], i]

Answer 2

您可以使用collections.Counter在O(n)中完成:

from collections import Counter
def two_sum(nums: list[int], target: int) -> tuple[int, int]:
c = Counter(nums)
for a in c:
b = target - a
if c[b] >= 1 + (a == b):
return a, b

构建Counter是O(n)，遍历它也是O(n)，检查迭代中的元素是O(1)。