LeetCode上的两个和

Question

我正在尝试做一个LeetCode问题:

给定一个整数数组,找到两个数字,使它们加起来一个特定的目标数.

函数twoSum应返回两个数字的索引,以便它们加起来到目标,其中index1必须小于index2.请注意,您返回的答案(index1和index2)不是从零开始的.

您可以假设每个输入都只有一个解决方案.

输入:数字= {2,7,11,15},目标= 9输出:index1 = 1,index2 = 2

第一次尝试是使用两个for循环,这给了我O(n ^ 2),不幸的是它没有通过.因此我尝试使用:

target - current = index

并搜索索引是否存在于字典中.

这是我的代码:

class Solution:
    def twoSum(self, nums, target):
        dic = {}

        #A number can appear twice inside the same index, so I use a list
        for i in xrange(0, len(nums)):
            try:
                dic[nums[i]].append(i)
            except:
                dic[nums[i]] = []
                dic[nums[i]].append(i)

        try:
            for items_1 in dic[nums[i]]:
                for items_2 in dic[target-nums[i]]:
                    if(items_1+1 != items_2+1):
                        l = []
                        if(items_2+1 > items_1+1):
                            l.append(items_1+1)
                            l.append(items_2+1)
                        else:
                            l.append(items_2+1)
                            l.append(items_1+1)
                        return l
        except:
            pass

我在本地开发了这个,并且我能够得到LeetCode抱怨的测试用例之一的正确结果:[ - 3,4,3,90],0

我得到的输出是[1,3],但是在LeetCode上它返回null,有人知道为什么会发生这种情况吗？

Answer 1

你想要这些东西:

#! python3

def two_sum(arr,targ):
    look_for = {}
    for n,x in enumerate(arr,1):
        try:
            return look_for[x], n
        except KeyError:
            look_for.setdefault(targ - x,n)

a = (2,7,1,15)
t = 9
print(two_sum(a,t))  # (1,2)

a = (-3,4,3,90)
t = 0
print(two_sum(a,t))  # (1,3)

在这里,您可以根据需要构建值字典.字典由您正在寻找的值键入,并且对于每个值,您可以跟踪其首次出现的索引.一旦你找到满足问题的价值,你就完成了.循环只有一个.

唯一的其他细节是为每个索引添加1以满足索引从1开始的荒谬要求.就像那将教你Python编程.

使用setdefault函数将键添加到字典中,因为如果键已经存在,则要保留其值(最低索引).

Answer 2

def twosum(nums=(6, 7, 11, 15, 3, 6, 5, 3), target=6):
    lookup = dict(((v, i) for i, v in enumerate(nums)))
    return next(( (i+1, lookup.get(target-v)+1) 
            for i, v in enumerate(nums) 
                if lookup.get(target-v, i) != i), None)

我没有对此进行过广泛的测试,但基本逻辑应该是合理的.该算法可分为两个阶段:

1. 为nums中的所有索引,值对创建value-> index字典.请注意,您可以使用具有不同索引的多个值.在这种情况下,最高索引将存储在字典中,较低索引将被覆盖.当然,这种行为可以修改,但我不认为它需要解决这个问题,因为问题陈述的一部分是这样的:"你可以假设每个输入都只有一个解决方案." 因此,每个输入都有一个唯一的输出,所以我们永远不必担心返回索引的"错误对".

2. 循环枚举nums,获取i索引和v值.检查是否target-v是我们创建的字典中的键,同时断言该键指向的值不是 i.如果这是真的,请返回元组i+1, lookup.get(target-v)+1.

Answer 3

这个答案使用从零开始的索引，因为这是正常的索引方式，而不是从一开始的索引。它还使用描述性变量名称，并且是为了理解而编写的。

from typing import List, Tuple

def twosum_indices_linear(nums: List[int], target: int) -> Tuple[int, int]:
    numtoindexmap = {}
    for num1_index, num1 in enumerate(nums):
        num2 = target - num1
        try:
            num2_index = numtoindexmap[num2]
        except KeyError:
            numtoindexmap[num1] = num1_index  
            # Note: Use `numtoindexmap.setdefault(num1, num1_index)` instead for lowest num1_index.
        else:
            return tuple(sorted([num1_index, num2_index]))

例子：

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

print(twosum_indices_linear([3, 3], 6))
(0, 1)

print(twosum_indices_linear([6, 7, 11, 15, 3, 6, 5, 3], 6))
(4, 7)

信用：乔格的回答

Answer 4

我刚刚通过了以下代码.为了获得有效的字典和笔记,只有一个解决方案.在逐个保存查找字典中的num时,搜索保存的查找字典中的target-num.当nums中有两个相同的值时,此方法可以节省空间并防止索引覆盖.

def twosum(self, nums, target):
    lookup = {}
    for cnt, num in enumerate(nums):
        if target - num in lookup:
            return lookup[target-num], cnt
        lookup[num] = cnt