leetcode 两数之和 Python 求解答

[a476286557]

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

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

示例:

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

因为 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)

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

[hand515]

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

[Kilerd]

list.append(index1)

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

[a476286557]

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

[hand515]

我看错。。

[Ryans]

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]

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

[casparchen]

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

[ballshapesdsd]

这不是第一题么。。。

[sendohzhang]

@Ryans

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

[lyog]

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

[singed]

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

[ingin]

有点 low

[maichael]

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

比如[3, 3]，target 6。

[a476286557]

@maichael 哈哈 我也发现了 。

[mrlcy]

"""
@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]

'''
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]

假定数组是 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]

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]

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]

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]

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

[swulling]

标准答案哈希表，On

[ayyll]

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

[huanyouchen]

通过字典构建一个哈希表：
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