Python中如何解答LeetCode两数之和问题
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 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)
我想问问为这个为什么不对？谢谢
Python中如何解答LeetCode两数之和问题
两数之和是LeetCode的经典入门题，核心思路是用哈希表（Python字典）来优化查找。直接上代码：
def two_sum(nums, target):
# 创建一个空字典来存储数字和它的索引
num_map = {}
# 遍历数组
for i, num in enumerate(nums):
# 计算需要的补数
complement = target - num
# 如果补数已经在字典中，直接返回结果
if complement in num_map:
return [num_map[complement], i]
# 否则将当前数字和索引存入字典
num_map[num] = i
# 题目保证有解，这里返回空列表以防万一
return []
关键点解析：
- 时间复杂度O(n)：只遍历一次数组，字典查找是O(1)
- 空间复杂度O(n)：最坏情况需要存储所有数字
- 核心思想：边遍历边记录，用空间换时间
测试一下：
print(two_sum([2, 7, 11, 15], 9)) # 输出 [0, 1]
print(two_sum([3, 2, 4], 6)) # 输出 [1, 2]
print(two_sum([3, 3], 6)) # 输出 [0, 1]
暴力解法是两层循环O(n²)，这个哈希表解法是最优解。记住这个“补数查找”模式，很多类似问题都能套用。
一句话建议：用字典存遍历过的值，实现O(n)时间复杂度的查找。
list.append(index1)
你只把第二个数的 index 放进去了。第一个数(i)的 index 没放进去。 而且找到之后 append 之后，应该直接 return
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) 暴力算法
for i, x in enumerate(nums):
for j, y in enumerate(nums):
if i != j and x + y == target:
print(x, y)
“”"
A: array
key: key word
left: left side index of the array.
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)的实现， 和你的思路类似。代码没有测试。
‘’‘
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]]
假定数组是 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))
js
/**
* {number[]} nums
* {number} target
* {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/
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
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]
