python 给定一个排序数组arr,找到三个i < k < n使得arr[i] + arr[k] + arr[n] = t

w7t8yxp5  于 2023-06-28  发布在  Python
关注(0)|答案(1)|浏览(150)

我试图解决这个问题,给定一个排序数组arr,找到三个索引ikni < 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))

我使用的是三个指针,但情况是无限的,什么是最好的时间复杂度算法?

igetnqfo

igetnqfo1#

这可以更简单地完成。只需迭代in,使它们始终相隔至少2(因此它们之间有k的空间)。然后检查tlst[i] + lst[n]之间的差异是否在它们之间,并将其索引到k中。

def threeSumSort(lst, t):
    for i in range(len(lst)-1):
        first = lst[i]
        if first > t:
            break

        for n in range(i+2, len(lst)):
            last = lst[n]
            middle = t - first - last
            if middle < lst[0]:
                break

            try:
                k = lst.index(middle, i+1, n)
                return i, k, n
            except ValueError:
                pass

lst = [0,2,3,5,10,13]
print(threeSumSort(lst, 8)) # (0, 2, 3)

相关问题