在数组中查找所有三元组，使它们的和小于或等于给定的值。

Question

这是最近在面试中问到我的一个朋友的问题，除了简单的O(n³)解法，我们不知道是否有更好的算法。

是否有更优的算法呢？

问题是要在整数数组中找到所有三元组，使它们的和小于或等于给定的总和S。

注意：我在SO上看到过其他类似的问题，其性能为O(n²log n)，但它们都解决的是这个问题的更简单版本，如 arr[i] + arr[j] + arr[k] = S 或者他们只检查是否存在这样的三元组。

我的问题是找出所有i,j,k，使得arr[i] + arr[j] + arr[k] <= S。

- user2250246

---

寻找所有满足 i、j 和 k 的三元组 (i,j,k)，使得 ijk = n。 - Bharel

Answer 1

从最坏情况的渐进角度来看，没有比这个算法更好的了，因为输出的大小可能是O(n³)。

例如，让数组成为数字1到n。 让S = 3n。 显然，任何三个数组元素的子集都将小于S，并且有(n choose 3) = O(n³)个子集。

有一些方法可以加速非最坏情况。 例如，尝试先对数组进行排序。 这应该会给你一些提示。

- tskuzzy

Answer 2

我有一个想法，但不确定它是否有效。

首先进行预处理（删除元素 > S）并对数组进行排序。

然后，在你选择arr[i]和arr[j]时，其中i<j，你可以在剩余的array[j+1...n]中二分搜索S - arr[i] - arr[j]。一旦你二分搜索到索引m，k可能位于j+1和m之间。

我认为这可能会降低复杂度。你觉得呢？

- Annie Kim

---

是的，我认为这将把复杂度降低到n2.log(n)。 - user2250246

方法可以稍微改进一下，在对A进行排序和过滤后，您将得到长度为n的B数组。然后，您需要迭代数组B [i]的元素并检测适合下一个公式的窗口B [j..k]： ... <code> j = 1; if (B [i] + B [j] <= S) { k = binarySearch（B，B [j] + B [i]）; 循环遍历j..k并打印。 } </code> - zubrabubra

你是对的，如果是负数可能会出错。 - zubrabubra

+1 分钟介绍三个有用的步骤——减少问题规模（删除 >S 元素），排序，以及为第三个元素引入二分查找。 - Ram Narasimhan

不需要检查@tskuzzy的答案。 - Ajk_P

Answer 3

这个会有什么复杂度？

如果应用于已排序的列表（升序），f 简单地按顺序一一列出三元组，使它们的总和小于等于s，而不创建重复项或扫描超过第一个太大的元素。

Haskell 代码：

f []     s result = if length result == 3 then [result] else []
f (x:xs) s result
  | length result == 3   = [result]
  | x + sum result > s   = []
  | otherwise            = f xs s (x:result) ++ f xs s result

输出：

*Main> length $ f [1..300] 300 []
731375
(5.09 secs, 402637784 bytes)

*Main> f [1..10] 13 []
[[3,2,1],[4,2,1],[5,2,1],[6,2,1],[7,2,1],[8,2,1],[9,2,1],[10,2,1],[4,3,1]
,[5,3,1],[6,3,1],[7,3,1],[8,3,1],[9,3,1],[5,4,1],[6,4,1],[7,4,1],[8,4,1]
,[6,5,1],[7,5,1],[4,3,2],[5,3,2],[6,3,2],[7,3,2],[8,3,2],[5,4,2],[6,4,2]
,[7,4,2],[6,5,2],[5,4,3],[6,4,3]]

- גלעד ברקן

Answer 4

我将保留原来的答案，但实际上可以用O(n)解决。我的新解决方案使用队列来跟踪三元组。它仅返回三元组的数量，但如果需要跟踪三元组列表，你可以很容易地创建一个列表来完成。

    class Queue (object):
      def __init__ (self):
        self.queue = []
        self.itemCount = 0

      def enqueue (self, item):
        self.queue.append (item)
        self.itemCount += 1

      def dequeue (self):
        self.itemCount += 1
        return (self.queue.pop(0))


    def findAllTriplets(li,S):
      if len(li) < 3:
        return "Not enough elements for triplets"
      tQ = Queue() # Queue to keep track of data
      tripletNum = 0 # Integer to track number of triplets to be returned
      tripletSum = 0 # Value of sum of consecutive list items for tripletNum evaluation
      for number in li:
        # Add the number to the queue immediately and add it to the current triplet sum
        tQ.enqueue(number)
        tripletSum += number
        # For the first 3 numbers only enqueue and add to the sum
        if tQ.itemCount < 3:
          continue
        # Afterwards, check if the sum of the latest three is less than S
        else:
          if(tripletSum <= S):
            tripletNum += 1
          # Dequeue the oldest element in the queue and subtract it from the tracked triplet sum
          tripletSum -= tQ.dequeue()
      return tripletNum

我认为这个算法应该可以在O(N²)的时间内完成，不过你需要提前对数组进行排序。

实际上，我的做法是找到所有可能的三元组，其中第一个索引i为零，下一个索引为j，通过搜索其余索引(k)中所有小于或等于x（或您的情况下的S）的和。之后，我将j增加1并重复此过程。一旦j到达数组的末尾，我就会从i + 1开始重新开始该过程，并继续进行，直到i等于倒数第二个索引值（因为此时没有可能的三元组了）。

Python代码

def numTriplets(a,x):
   if len(a) < 3:
       return None
   i = 0
   j = 1
   triplets = []
   while True:
      for k in range(j+1,len(a)):
         if a[i] + a[j] + a[k] <= x:
            triplets.append([i,j,k])
      j += 1
      if j == len(a) - 1:
         i += 1
         j = i + 1
      if i == len(a) - 2:
         return triplets

- Nathan R

Answer 5

这个问题可以在O(n²)的复杂度下解决。

首先对数字进行排序→ O(nlog(n))

现在从前面开始，每次固定一个数字。现在问题变成在已排序的数组中找到两个数，它们的和小于或等于给定的总和。使用两个指针，一个从开头，一个从结尾，这可以在O(n)的时间内解决。因此，总体复杂度为O(n²)。

- vivek