leetcode 两数之和 Python 求解答

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 我写的代码如下：
class Solution:
    def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    list = []
    for i in nums:
        a = target - i
        if a != i:
            if a in nums:
                index1 = nums.index(i)
                list.append(index1)

我想问问为这个为什么不对？谢谢

nbsp

nums

Target

list

24 条回复 • 2018-06-30 20:43:57 +08:00

hand515

2018-06-29 14:44:06 +08:00

target - i ??
target - nums[i] 吧

Kilerd

2018-06-29 14:47:13 +08:00

list.append(index1)

你只把第二个数的 index 放进去了。第一个数(i)的 index 没放进去。而且找到之后 append 之后，应该直接 return

a476286557

2018-06-29 15:01:36 +08:00

@hand515 我遍历的是列表并没有遍历它的长度

hand515

2018-06-29 15:03:59 +08:00

我看错。。

Ryans

2018-06-29 15:13:13 +08:00

for i in range(len(nums)):
for j in range(i):
if ( nums[j] == target - nums[i]):
return [j,i]
return [-1,-1]

O(n^2) 暴力算法

lyog

2018-06-29 15:43:36 +08:00 via iPhone

hashMap 解决，key 为 target-nums[i]，value 为 i

casparchen

2018-06-29 15:46:04 +08:00 via iPhone

[1,3,4,3], target=6

ballshapesdsd

2018-06-29 15:46:55 +08:00

这不是第一题么。。。

sendohzhang

2018-06-29 15:49:54 +08:00

@Ryans

for j in range(i) ??? 应该是 for j in range(len(nums))吧

lyog

2018-06-29 15:52:20 +08:00 via iPhone

@lyog 至于楼主问题，最后加个 list.append(nums.index （ a ）)解决

singed

2018-06-29 16:16:38 +08:00

for i, x in enumerate(nums):
for j, y in enumerate(nums):
if i != j and x + y == target:
print(x, y)

ingin

2018-06-29 16:37:36 +08:00

有点 low

maichael

2018-06-29 16:54:56 +08:00

当两个数相等的情况下你的就炸了。

比如[3, 3]，target 6。

a476286557

2018-06-29 18:04:10 +08:00

@maichael 哈哈我也发现了。

mrlcy

2018-06-29 19:35:26 +08:00

"""
@param A: array
@param key: key word
@param left: left side index of the array.
@param right: right side index of the array.
"""
def binary_search(A, key, left, right):
"""
imp
"""
def twoSums(self, nums, target):
for i in range(0, len(nums)):
key = target - nums[i]
index = binary_search(nums, key, i, len(nums)-1)
if (r is not -1):
print((nums[i], nums[index]))

nlog(n)的实现，和你的思路类似。代码没有测试。

fushall

2018-06-29 20:07:30 +08:00

'''
1. 两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

'''

class Solution:
# 执行用时：80 ms
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
nums = [(value, index) for index, value in enumerate(nums)]
nums.sort(key=lambda k:k[0])
c = 0
for x in nums:
c += 1
v = target - x[0]
for y in nums[c:]:
if not (y[0] - v):
return [x[1], y[1]]

necomancer

2018-06-29 23:50:33 +08:00

假定数组是 a，长度是 n, [ (i, j) for i,x in enumerate(a) for j,y in enumerate(a) if x + y == target and i<j ] 比较直观，复杂度是 O(n^2)，大致看了下，至少你的 a!=i 就不允许列表中出现重复元素；并且最后也少放了另一个元素 a 的标号在结果里。

第二个就是用 binary_search，当然，假定你的数组 a 是排好序的：

[ idxes for idxes in ( (i, binary_search(target - x, i+1, n)) for i, x in enumerate(a) ) if idxes[1] != -1 ]，比如用楼上那个失败返回 -1 的 binary_search，这样是 O(nlog(n))

BaffinLee

2018-06-30 00:07:46 +08:00

js

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
var hash = {};
var len = nums.length;
for (var i = 0; i < len; i++) {
if (nums[i] in hash) return [hash[nums[i]], i];
hash[target - nums[i]] = i
}
return [-1, -1];
};

https://baffinlee.github.io/leetcode-javascript/

necomancer

2018-06-30 00:13:53 +08:00

EDIT:
1. [ (i, j) for i,x in enumerate(a) for j,y in enumerate(a) if i<j and x + y == target ]
2. [ idxes for idxes in ( (i, binary_search(a, target - x, i+1, n-1) ) for i, x in enumerate(a) ) if idxes[1] != -1 ]

def binary_search(arr, hkey, start, end):
....while start <= end:
........mid = start + (end - start) // 2
........if arr[mid] < hkey:
............start = mid + 1
........elif arr[mid] > hkey:
............end = mid - 1
........else:
............return mid
....return -1

IceCola1

2018-06-30 00:20:46 +08:00

class Solution:
def twoSum(self,nums, target):
sd={}
for index_i,i in enumerate(nums):
if sd.get(target-i)!=target-i:
sd[i]=i
else:
return [nums.index(target-i),index_i]

IceCola1

2018-06-30 00:22:22 +08:00

你们的都好长啊，我这个 44ms

swulling

2018-06-30 06:59:54 +08:00 via iPhone

标准答案哈希表，On

ayyll

2018-06-30 08:24:30 +08:00 via Android

@swulling 楼上一堆暴力。。这题哈希应该不难想到吧。。。。

huanyouchen

2018-06-30 20:43:57 +08:00

通过字典构建一个哈希表：
class Solution:
def twoSum(self, nums, target):
dic = {}
for i,num in enumerate(nums):
if num in dic:
return [dic[num],i]
else:
dic[target-num] = i