Python：如何防止双重循环返回列表中相同的索引值

Question

我目前正在Leetcode上解决第1个问题，名为“Two Sum”。

给定一个整数数组，返回两个数的索引，使它们相加等于特定目标值。

你可以假设每个输入都只有一种解决方案，并且不能重复使用相同的元素。

例如，给定nums=[2,7,11,15]和target=9，因为nums [0]+nums[1]=2+7=9，所以返回[0，1]。

我的代码是：

def twosum_indices(nums, target):
    for i in nums:
        for v in nums[i + 1:]:
            if i + v == target:
                return nums.index(i), nums.index(v)

在这个问题中，nums是一个整数列表，程序必须返回两个不同的索引列表，使它们的真实值加起来等于给定的目标值。虽然这在大多数测试用例中都很好用，但是在像[3,3]这样的列表中，两个值相同，程序会返回两次相同的索引，如[0,0]，而不是返回实际答案[0,1]。为什么会出现这种情况呢？

- Samvit Agarwal

---

你正在尝试天真的暴力方法，它是O(n**2)，因此是错误的（因为当他们使用真实数据攻击您时，它将花费太长时间）。正确答案是O(n)。然而，你的尝试失败了，因为i是一个数字，但你正在将它用作索引。 - Kenny Ostrom

只有当数组已排序时，时间复杂度才为O(n)，我想是这样的。 - cs95

@cᴏʟᴅsᴘᴇᴇᴅ 不要，使用 dict，遍历序列并将索引添加到 dict 中，对于 seq 中的每个元素，检查其补数是否在 dict 中。 - juanpa.arrivillaga

你又把数字i当作索引来处理了，但实际上它不是，所以第二个循环是错误的。请在调试器中逐步执行它。此外，如果你传入target=6，nums=[3,3]，你发布的代码将返回None。你永远不会进入if语句，只是简单地跳出函数的末尾（这意味着在Python中返回None）。 - Kenny Ostrom

即使您修复了索引，当您调用始终返回第一个索引的nums.index时，它也将毫无意义。尝试这个 - 对于i在范围(len(nums)中：对于j在范围(i，len(nums)中：如果nums[i] == nums[j]：返回i，j（此外，这适用于小输入，但速度太慢...他们最终希望您想出一种方法进行两次通行而不是将每个项目与其他每个项目进行比较，但我已经尽力不让您知道那是什么） - Kenny Ostrom

Answer 1

你的代码中有多个问题，其中最严重的是没有使用enumerate而是使用了list.index。例如，[3,3].index(3)永远都是0。

本答案的重点并不是找到最高效的解决方案，而是改进你的特定方法。你也可以参考O(n) 解决方案。

理解列表推导式

在此之前，请先理解列表推导式中多个for循环的用法。

def sums(nums):
    return [x + y for x in nums for y in nums[:x]]

上述内容等同于：

def sums(nums):
    output = []
    for x in nums:
       for y in nums[:x]:
           output.append(x + y)
    return output

使用链式生成器表达式的解决方案

def twosum_indices(nums, target):
    return next((i, j) for i in range(len(nums)) for j in range(len(nums[:i])) if (nums[i] + nums[j] == target))

示例:

print(sorted(twosum_indices([2, 7, 11, 15], 9)))
[0, 1]

print(sorted(twosum_indices([3, 3], 6)))
[0, 1]

使用itertools的生成器表达式解决方案

使用itertools会更简单一些：

import itertools

def twosum_indices_it(nums, target):
    return next((i, j) for (i, x), (j, y) in itertools.combinations(enumerate(nums), 2) if (x + y == target))

示例：

print(sorted(twosum_indices_it([2, 7, 11, 15], 9)))
[0, 1]

print(sorted(twosum_indices_it([3, 3], 6)))
[0, 1]

- Asclepius

Answer 2

#! /usr/bin/env python3


def two_sum_indices(nums, target):

    def dup(i, j):
        return i == j

    d = {num: i
         for i, num in enumerate(nums)}

    for i, num in enumerate(nums):
        if target - num in d:
            if not dup(i, d[target - num]):
                return i, d[target - num]
    return -1, -1


if __name__ == '__main__':

    print(two_sum_indices([2, 7, 11, 15], target=9))
    print(two_sum_indices([3], target=6))
    print(two_sum_indices([3, 3], target=6))

- J_H

Answer 3

def twosum_indices(nums, target):
    for i in range(len(nums)):
        for v in range(len(nums)):
            if nums[i] + nums[v] == target and i != v:
                return i, v

- Fibo36

---

如果你运行这个程序，你会发现它仍然有相同的错误输出。 - Kenny Ostrom

@KennyOstrom 这段代码在我的电脑上可以运行，你得到的结果是什么？ - Fibo36

nums = [3, 3]，target = 6，result = [0, 0]，期望结果为[0, 1]，因为您依赖于nums.index，它将返回第一个出现的位置。 - Kenny Ostrom

@Fibo36 现在它可以工作了，这很好，但计算复杂度仍然比必要的高。基本上，如果你需要检查 i != v，那么你的复杂度就比必要的高。你正在两次循环遍历数字对，这可能是可以避免的。 - Asclepius

@A-B-B 你能展示给我一个更有效的做法吗？ - Fibo36

@Fibo36 是的，一种方法是使用 for v in range(len(nums[:i])):。这样你就不需要 i != v 的检查了。 - Asclepius