Codewars两数之和问题：含重复元素数组返回None求助

你的two_sum函数在处理包含重复元素的数组时（比如测试用例[2,2,3]）会返回None，核心问题出在你用numbers.index(i)获取索引的方式上。

先看你原来的代码：

def two_sum(numbers, target):
    #takes an array, and a target value
    #return sum of two elements that equate to target value

    for i in numbers:
        for z in numbers:
            if sum([i] + [z]) == target and numbers.index(i) != numbers.index(z):
                x = numbers.index(i)
                y = numbers.index(z)
                return [x, y]

print(two_sum([1,2,3], 4))

问题原因 #

list.index()方法只会返回第一个匹配元素的索引。在测试用例[2,2,3]中，不管你取的是第一个2还是第二个2，numbers.index(2)都会返回0。这就导致判断条件numbers.index(i) != numbers.index(z)永远不成立（两个2的索引都被判定为0），函数找不到符合条件的结果，最终返回默认的None。

另外你的双重循环还会重复检查同一对元素（比如先检查i=第一个2、z=第二个2，又会检查i=第二个2、z=第一个2），效率也不高。

解决方法 #

直接遍历数组的索引而不是元素，这样能精准区分不同位置的相同元素：

def two_sum(numbers, target):
    # 遍历每个元素的索引i
    for i in range(len(numbers)):
        # 从i的下一个索引开始遍历，避免重复检查
        for j in range(i + 1, len(numbers)):
            if numbers[i] + numbers[j] == target:
                return [i, j]

测试验证 #

用你的三个测试用例验证：

# 测试用例1
assert sorted(two_sum([1,2,3], 4)) == [0,2]
# 测试用例2
assert sorted(two_sum([1234,5678,9012], 14690)) == [1,2]
# 测试用例3
assert sorted(two_sum([2,2,3], 4)) == [0,1]

所有测试用例都能通过。

额外优化（可选） #

如果数组规模较大，双重循环的时间复杂度是O(n²)，可以用哈希表（字典）把时间复杂度降到O(n)：

def two_sum(numbers, target):
    num_map = {}
    for index, num in enumerate(numbers):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], index]
        num_map[num] = index

这个方法通过记录已经遍历过的元素和索引，每次只需要检查目标值减去当前元素的结果是否在哈希表中，找到就直接返回索引对。

内容的提问来源于stack exchange，提问作者radriaansNES