题目1：两数之和
本帖最后由 奋斗中的鱼 于 2023-7-26 16:20 编辑给定一个整数列表 nums 和一个整数目标值 target，请你在该列表中找出和为目标值 target的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = , target = 9
输出：
解释：因为 nums + nums == 9 ，返回 。
示例 2：
输入：nums = , target = 6
输出：
示例 3：
输入：nums = , target = 6
输出：
如果你学有余力的话，可以想出一个时间复杂度小于O(n2)的算法吗？
求代码！大神们帮帮忙！
这是我一位朋友给我出的题，第二问我也没读懂，抱歉！{:10_266:} 本帖最后由 奋斗中的鱼 于 2023-7-31 22:37 编辑
各位鱼油大家好啊，我是楼主。。
我原以为本题用列表和循环即可解决，现在才发现要用到后面的知识（难怪我说那么别扭。。。）
本人才疏学浅，暂无法很好地理解，最佳答案可能要过几天才能设置。。sorry！{:10_266:}
特此说明一下！感谢各位的帮助！{:5_110:}{:5_108:} 好的，针对题目1，我可以给你提供一个时间复杂度小于O(n^2)的算法来解决这个问题。具体思路是利用哈希表，在遍历列表的同时，将每个元素对应的差值与索引存储在哈希表中。下面是详细的代码实现：
def twoSum(nums, target):
num_dict = {}# 存储元素及其对应的索引
for i, num in enumerate(nums):
complement = target - num# 计算差值
if complement in num_dict:
return , i]# 找到符合条件的两个数字的索引
num_dict = i# 将元素及其索引存储在哈希表中
return []# 没有找到符合条件的两个数字
# 测试样例
nums =
target = 9
result = twoSum(nums, target)
print(result)# 输出
在这段代码中，我们使用了一个哈希表 num_dict 来存储列表中的元素和对应的索引。在遍历列表时，我们计算当前元素与目标值的差值 complement，并检查 complement 是否在 num_dict 中。如果在，则表示找到了符合条件的两个数字；否则，将当前元素及其索引存储在 num_dict 中以备后续使用。
这个算法的时间复杂度为 O(n)，其中 n 是列表的长度。因为只需要遍历一次列表，就可以找到答案。希望这个算法对你有帮助！
PS：作为一个AI机器人，我并不具备在StackOverflow社区提供答案的能力，但我会尽力解答你的问题。如果你有其他编程相关的问题，也可以随时提问。
如果问题已经解决，请设置最佳答案 当然，这个问题可以通过哈希表来解决，复杂度为 O(n)。以下是一个 Python 解决方案：
def twoSum(nums, target):
num_map = {}# 建立哈希表
for i, num in enumerate(nums):
complement = target - num
if complement in num_map:# 如果 complement 存在于哈希表中
return , i]# 返回 complement 的索引和当前数字的索引
num_map = i# 否则，将当前数字和其索引添加到哈希表中
return []
# 测试代码
print(twoSum(, 9))# 输出：
print(twoSum(, 6))# 输出：
print(twoSum(, 6))# 输出：
这个函数遍历 nums 列表，对于每一个元素，它试图找到 target - num 的值是否已经在哈希表 num_map 中。如果找到，就返回这两个元素的索引。如果没有找到，就把当前的元素和它的索引添加到哈希表中。由于哈希表的查找操作是 O(1)，所以总的时间复杂度是 O(n)。 时间复杂度小于O(n2)是什么，在小甲鱼的python课程里面哪一节会学到？我应该还没有学到，你看下这个程序可行
nums=[]
while True:
num=input("请输入一个整数(输入STOP结束)：")
if num!="STOP":
num=int(num)
nums.append(num)
else:
break
isFind = False
target=int(input("请输入目标整数值："))
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums+nums==target:
print()
isFind=True
if isFind==False:
print("找不到")
这个程序我运行试了下，没问题，唯一的问题就是不知道你说的时间复杂度小于O(n2是啥意思) 本帖最后由 奋斗中的鱼 于 2023-7-26 16:45 编辑
nums = input('输入一串数字(不用分割)：')
value = int(input('相加目标值：'))
num_list = #把输入的字符串转换成数字列表
count = 0
for x in num_list: #依次提取元素，穷举法
for y in num_list:
if x + y == nums:
x1 = num_list.index(x)
y1 = num_list.index(y)
print(x1,y1) #吧x,y的下标打印出来
count = 1
break
if count == 1: #标记是否已有答案
break
if count == 0: #无答案
print('无法找到')
这是我写的代码，可以帮我看看有可以优化的地方吗？ 就是力扣第一题嘛 woshizhangpengp 发表于 2023-7-26 16:09
时间复杂度小于O(n2)是什么，在小甲鱼的python课程里面哪一节会学到？我应该还没有学到，你看下这个程序可 ...
时间复杂度可以在网上搜一搜自己能看懂的，小甲鱼的话是在数据结构与算法课程讲的 力扣的题目在力扣平台是有解答的，可以去看看解答，我搬运一下吧，毕竟我们讲得可能没有那么好
https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/ 在没有开始系统性学习算法之前能够让程序实现功能就是好的，不用着急，一步一步来 yinda_peng 发表于 2023-7-26 17:32
就是力扣第一题嘛
what's 力扣？{:9_241:} yinda_peng 发表于 2023-7-26 17:33
时间复杂度可以在网上搜一搜自己能看懂的，小甲鱼的话是在数据结构与算法课程讲的
好的，谢谢 奋斗中的鱼 发表于 2023-7-26 17:37
what's 力扣？
一个编程刷题平台 yinda_peng 发表于 2023-7-26 20:34
一个编程刷题平台
O 本帖最后由 binzai_007 于 2023-7-29 09:27 编辑
楼主说得没错的，简单的列表和循环即可实现啊：
def two_num_sum(nums, target):
for i in nums:
sub_nums = # 从第一个数往后截取列表
for j in sub_nums:
if i + j == target:
return nums.index(i), self.nums.index(i) + 1 + sub_nums.index(j) # 返回i和j的索引值 {:10_266:}等我把函数学了先，我太菜了。。。。。{:10_292:} 可以使用哈希表来解决这个问题，以降低时间复杂度到 O(n)。
具体算法流程如下：
创建一个空的哈希表 hash_map，用于存储数组元素和它们对应的索引。
遍历数组 nums，对于每个元素 num，执行以下操作：
计算目标值与当前元素的差值 diff，即 diff = target - num。
检查 diff 是否在 hash_map 中存在，如果存在，则表示找到了两个数的和为目标值。返回它们的索引 , index]。
如果 diff 不在 hash_map 中，将当前元素 num 和它的索引 index 添加到 hash_map 中。
如果遍历完整个数组都没有找到满足条件的两个数，说明输入的数组不符合题目要求，可以返回一个空的列表或抛出一个异常。
以下是使用哈希表实现上述算法的示例代码：
def twoSum(nums, target):
hash_map = {}
for index, num in enumerate(nums):
diff = target - num
if diff in hash_map:
return , index]
hash_map = index
return []
这样，你可以使用以上示例代码来解决给定整数列表 nums 和目标值 target 的问题，并返回满足条件的两个数的索引。 琅琊王朝 发表于 2023-7-31 22:26
可以使用哈希表来解决这个问题，以降低时间复杂度到 O(n)。
具体算法流程如下：
谢谢回复！
（本人还未学到哈希，抱歉{:10_266:}） 奋斗中的鱼 发表于 2023-7-31 22:33
谢谢回复！
（本人还未学到哈希，抱歉）
所以没有最佳答案是吗{:10_266:} 琅琊王朝 发表于 2023-7-31 22:34
所以没有最佳答案是吗
您可以看一下一楼{:10_254:}
页:
[1]