给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
给定 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)
我想问问为这个为什么不对?谢谢
1
hand515 2018-06-29 14:44:06 +08:00
target - i ??
target - nums[i] 吧 |
2
Kilerd 2018-06-29 14:47:13 +08:00
list.append(index1)
你只把第二个数的 index 放进去了。第一个数(i)的 index 没放进去。 而且找到之后 append 之后,应该直接 return |
3
a476286557 OP @hand515 我遍历的是列表 并没有遍历它的长度
|
4
hand515 2018-06-29 15:03:59 +08:00
我看错。。
|
5
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) 暴力算法 |
6
lyog 2018-06-29 15:43:36 +08:00 via iPhone
hashMap 解决,key 为 target-nums[i],value 为 i
|
7
casparchen 2018-06-29 15:46:04 +08:00 via iPhone
[1,3,4,3], target=6
|
8
ballshapesdsd 2018-06-29 15:46:55 +08:00
这不是第一题么。。。
|
9
sendohzhang 2018-06-29 15:49:54 +08:00
|
11
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) |
12
ingin 2018-06-29 16:37:36 +08:00
有点 low |
13
maichael 2018-06-29 16:54:56 +08:00
当两个数相等的情况下你的就炸了。
比如[3, 3],target 6。 |
14
a476286557 OP @maichael 哈哈 我也发现了 。
|
15
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)的实现, 和你的思路类似。代码没有测试。 |
16
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]] |
17
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)) |
18
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/ |
19
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 |
20
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] |
21
IceCola1 2018-06-30 00:22:22 +08:00
你们的都好长啊,我这个 44ms
|
22
swulling 2018-06-30 06:59:54 +08:00 via iPhone
标准答案哈希表,On
|
24
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 |