首页 文章

Python：防止双重for循环返回列表的相同索引

提问于
浏览 次
3

我目前正在研究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] . 为什么会这样？

python algorithm

3 回答

  • 1
    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
    回复于
  • 3

    您的代码中存在多个错误，其中最少的错误是使用 enumerate 而不是 list.index . 例如， [3, 3].index(3) 当然总是0 .

    这个答案的重点不是达到最有效的解决方案，而是要改进您的具体方法 . 您也可以选择查看O(n) solution .

    了解列表推导

    作为先决条件，首先要了解multiple for loops can exist in a list comprehension .

    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]
    回复于
  • 0
    #! /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))
    回复于

相关问题