Python LeetCode 上的两个和
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/30021060/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Two Sum on LeetCode
提问by user1157751
I'm trying to do a LeetCode question:
我正在尝试做一个 LeetCode 问题：
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
给定一个整数数组，找到两个数字，使它们相加为特定的目标数字。
函数 twoSum 应该返回两个数字的索引，使它们相加为目标，其中 index1 必须小于 index2。请注意，您返回的答案（index1 和 index2）不是从零开始的。
您可以假设每个输入都只有一个解决方案。
输入：number={2, 7, 11, 15}, target=9 输出：index1=1, index2=2
The first try was using two for loops, which gave me O(n^2), and unfortunately it didn't pass. Hence I tried to use:
第一次尝试是使用两个 for 循环，这给了我 O(n^2)，不幸的是它没有通过。因此我尝试使用：
target - current = index
And search for if the index does exists on a dictionary.
并搜索索引是否存在于字典中。
This is my code:
这是我的代码：
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
I developed this locally, and I was able get the correct result with one of the test case that LeetCode was complaining: [-3,4,3,90], 0
我在本地开发了这个，并且我能够通过 LeetCode 抱怨的测试用例之一得到正确的结果：[-3,4,3,90], 0
The output I got was [1, 3], but on LeetCode it returned null, does anybody know why this would happen?
我得到的输出是 [1, 3]，但在 LeetCode 上它返回 null，有人知道为什么会发生这种情况吗？
采纳答案by Shashank
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)
I have not tested this extensively but the basic logic should be sound. This algorithm can be broken up into two stages:
我没有对此进行广泛的测试，但基本逻辑应该是合理的。该算法可以分为两个阶段：
Create a dictionary of value->index for all index, value pairs in nums. Note that you can have multiple values with different indices. In this case, the highest index will be stored in the dictionary and lower indexes will be overwritten. This behavior can be modified, of course, but I don't believe it needs to be for this problem because part of the problem statement is this: "You may assume that each input would have exactly one solution." Thus, each input has a single unique output so we never have to worry about returning a "wrong-pair" of indices.
Loop through the enumeration of nums, getting
ias index, andvas value. Check iftarget-vis a key in the dictionary we created, and simultaneously assert that the value pointed to by that key is noti. If this is ever true, return the tuplei+1, lookup.get(target-v)+1.
为 nums 中的所有索引、值对创建一个 value->index 字典。请注意，您可以有多个具有不同索引的值。在这种情况下，最高索引将存储在字典中，而较低索引将被覆盖。当然，可以修改此行为，但我认为不需要针对此问题进行修改，因为问题陈述的一部分是：“您可能假设每个输入都只有一个解决方案。” 因此，每个输入都有一个唯一的输出，所以我们永远不必担心返回“错误对”的索引。
循环遍历 nums 的枚举，获取
i为索引和v值。检查 iftarget-v是我们创建的字典中的一个键，同时断言该键指向的值不是i。如果这是真的，则返回 tuplei+1, lookup.get(target-v)+1。
回答by Paul Cornelius
You want something along these lines:
你想要这样的东西：
#! 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)
Here you build the dictionary of values on an as-needed basis. The dictionary is keyed by the values you are seeking, and for each value you track the index of its first appearance. As soon as you come to a value that satisfies the problem, you're done. There is only one for loop.
在这里，您可以根据需要构建值字典。字典由您正在寻找的值作为键，并且对于每个值，您跟踪其首次出现的索引。一旦你得到一个满足问题的值，你就完成了。只有一个 for 循环。
The only other detail is to add 1 to each index to satisfy the ridiculous requirement that the indices be 1-based. Like that's going to teach you about Python programming.
唯一的其他细节是给每个索引加 1，以满足索引从 1 开始的荒谬要求。就像那会教你关于 Python 编程一样。
Keys are added to the dictionary using the setdefault function, since if the key is already present you want to keep its value (the lowest index).
使用 setdefault 函数将键添加到字典中，因为如果键已经存在，您希望保留其值（最低索引）。
回答by Iris
I have just passed the following codes. To take advantage the dictionary and the notes that there is one and only one solution. To search the target-num in the saved lookup dictionary when saving the num in the lookup dictionary one by one. This method could save the space and also prevent the index overwriting when there are two same values in the nums.
我刚刚通过了以下代码。利用字典和注释，只有一种解决方案。一一保存查找字典中的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
回答by Acumenus
This answer uses zero-based indexing since that's the normal way to index, not one-based indexing. It also uses descriptive variable names, and is written for comprehension.
这个答案使用从零开始的索引，因为这是正常的索引方式，而不是从一开始的索引。它还使用描述性变量名称，并且是为了理解而编写的。
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]))
Examples:
例子：
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)
Credit: answer by joeg
信用：乔格的回答
回答by Mohamed Abu ElGheit
this is my answer
这是我的答案
class Solution:
def twoSum(self, nums, target):
ls = []
for i in range(0, len(nums)):
item = target - nums[i]
nums[i] = "done"
if item in nums:
ls.append(i)
ls.append(nums.index(item))
return ls
回答by Yuan-Lu Chen
def twoSum(nums,target):
k={value:index for index, value in enumerate(nums)}
# using dictionary comprehesion to create a dictionary that maps value to index
ans=[[j,k[target-x]] for j,x in enumerate(nums) if target-x in k]
# use list comprehension to create a set of answers; make sure no key error by using 'if target-x in k'
ans=[x for x in ans if x[0] != x[1]]
# make sure the two indexes are not the same. E.g. twoSum([1,2,0],2) returns [[0,0],[0,1],[1,2],[2,1]]; and [0,0] is a wrong answer
return ans[0]
This solution is time efficient (faster than 80% of the solutions on leetcode), but takes lots memory.
该解决方案省时（比 leetcode 上 80% 的解决方案快），但需要大量内存。
回答by user3947485
I like
我喜欢
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)
above but it fails timedome due to call to enumerate taking too long for large arrays. Better to skip the enumerate and just keep a count of index:
上面但由于调用枚举对大型数组花费的时间太长而导致 timedome 失败。最好跳过枚举并保留索引计数：
def findCombo(l,target):
lookup = {}
n = 0
for x in l:
try:
return (n,lookup[x])
except KeyError:
lookup.setdefault (target-x,n)
n = n + 1
return None
Note:Python timedome question uses index starting at 0
注意：Python timedome 问题使用索引从 0 开始
回答by Prince Pipera
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
r = []
for i in range(len(nums)):
temp = target - nums[i]
if temp in r:
return [i,nums.index(temp)]
r.append(nums[i])
