python - 3SUM 到特定值
问题描述
我目前有一个解决方案,但仍然太慢了 300%。问题是从给定列表中找到总和为 n 的三个数字的子集。
goal = int(input().split()[1]) #The desired sum
numbers = list(map(int, input().split())) #User-inputted numbers
myDict = {} #Created so we can quickly check if a number is present in the list
for i in numbers: #The amount of each number is stored in the dict, eg. 439797: 2
if i in myDict:
myDict[i] += 1
else:
myDict[i] = 1
numbers = sorted(numbers)
for start in range(0, len(numbers)):
for end in range(1, len(numbers)):
myDict[numbers[start]] -= 1
myDict[numbers[end]] -= 1
#This is done so that the same number isn't used twice
if goal-numbers[start]-numbers[end] in myDict:
if myDict[goal-numbers[start]-numbers[end]] > 0:
print(goal-numbers[start]-numbers[end], numbers[start], numbers[end])
quit()
myDict[numbers[start]] += 1
myDict[numbers[end]] += 1
解决方案
您在内部循环中索引您的字典六次,这是完全没有必要的,并且可能占您运行时间的大部分。您可以只使用一个索引操作,而无需对字典进行任何修改:
for i in range(0, len(numbers)):
m = numbers[i]
for j in range(i + 1, len(numbers)):
n = numbers[j]
if n != m:
k = goal - m - n
if k != m and k != n and k in myDict:
# accept triple (m, n, k)
此外,正如评论中已经建议的那样,对输入进行排序没有意义。
更新:同样从评论中,您的内部循环从 1 开始。这大约使您的运行时间加倍。
更新 2:此外,鉴于不再需要字典中的计数,字典现在可以是一个集合(但不确定它是否会以任何有意义的方式影响性能。)
更新 3:添加了对n != m
.
推荐阅读
- postgresql - Postgresql函数执行过程
- ios - 如何以编程方式快速保存pdf
- php - 简单的 xero api oauth2 请求
- java - 生成 PKCS7 编码的数字签名 - Hwcrypto、itextPdf、USB Token
- java - 如何在 Java 中解析和求解方程字符串?
- javascript - Vue.js v-if 不重新渲染
- android - 如果未找到 Wi-Fi AP,则不调用 NetworkCallback 的 onUnavailable() 方法
- javascript - 从 JS 发布表单值数组
- module - 如何访问main.rs中的函数,该函数已写入同一包中rust的不同目录中的文件中
- reactjs - 无法使用 useState 以编程方式更改组件的值