我目前有一个解决方案,但仍然大约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
我完全同意shinobi,但如果你需要快速计算这些任务,那么C ++就是你的选择。代码如下所示:
for (int i = 0, i < len(numbers); i++) {
int m = numbers[i];
for (int j = i + 1, j < len(numbers); j++) {
int n = numbers[j];
if (n != m) {
int k = goal - m - n;
if (k != m && k != n && myDict[k]) {
doSomething();
}
}
}
你在内循环中将你的字典索引六次,这是完全没必要的,并且可能占你运行时间的大部分。您可以只使用一个索引操作,而无需对字典进行任何修改:
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
的检查。