主页 / 问题 / 1576286
Accepted
Глеб
Asked:2024-04-15 19:53:15 +0800 CST2024-04-15 19:53:15 +0800 CST

用 Leetcode 优化二和问题

  • 772

LeetCode有一个任务。条件是给你一个 intnums和 int的列表target，并且你需要返回两个数字相加的索引target。我写了下面的算法来解决这个问题：

def twoSum(self, nums: List[int], target: int) -> List[int]:
    if all(i <= 0 for i in nums): 
        nums = [abs(i) for i in nums]
        target = abs(target)
    for i in range(min(nums) - 1, target + 1):
        j = target - i
        if i != j:
            if i in nums and j in nums:
                return [nums.index(i), nums.index(j)]
        else:
            if nums.count(i) > 1:
                return [n for n, m in enumerate(nums) if m == i][:2]

他通过了基本测试，但未能通过大量测试 - 时间不够。如何对其进行优化？

python

1 个回答

  1. Best Answer

    使用字典 - 将元素：索引对放入其中。如果字典已经有一个键与当前元素形成所需的和，那么我们就找到了它。

    dct = dict()
for i, x in enumerate(nums):
    if target - x in dct:
        return [i, dct[target - x]]
    else:
        dct[x] = i

    另一种选择是对 [element,index] 对列表进行排序并从两端开始

    • 3

相关问题