我试图解决这个问题,给定一个排序数组arr
,找到三个索引i
,k
,n
和i < k < n
,使得arr[i] + arr[k] + arr[n] = t
。保证数组至少有一个解。
当我按照我的算法我得到了结果,然而,我得到了一个空列表作为结果,这是什么问题?
这是我的尝试:
def threeSumSort(lst, t):
res = []
i, n = 0, len(lst)-1
k = (n // 2)
while (i < k < n):
pt = lst[i] + lst[k] + lst[n]
if pt == t:
res.append([i+1, k+1,n+1])
return res
elif (pt > t):
if (pt - lst[k] - lst[n-1]) + lst[k-1] + lst[n-1] > t:
n -= 1
k -= 1
elif (pt - lst[k]) + lst[k-1] > t:
k -= 1
elif (pt - lst[n]) + lst[n-1] > t:
n -= 1
else:
if (pt - lst[k] - lst[i+1]) + lst[k+1] + lst[i+1] < t:
i += 1
k += 1
elif (pt - lst[k]) + lst[k+1] < t:
k += 1
elif (pt - lst[i]) + lst[i+1] < t:
i += 1
return res
lst = [0,2,3,5,10,13]
print(threeSumSort(lst, 8))
我使用的是三个指针,但情况是无限的,什么是最好的时间复杂度算法?
1条答案
按热度按时间igetnqfo1#
这可以更简单地完成。只需迭代
i
和n
,使它们始终相隔至少2(因此它们之间有k
的空间)。然后检查t
和lst[i] + lst[n]
之间的差异是否在它们之间,并将其索引到k
中。