algorithm - Find all triplets in array with sum less than or equal to given sum

Question

This was recently asked to a friend in an interview and we do not know of any solution other than the simple O(n³) one.

Is there some better algorithm?

The question is to find all triplets in an integer array whose sum is less than or equal to given sum S.

Note: I have seen other such problems on SO with performance O(n²log n) but all of them were solving the easier version of this problem like where arr[i] + arr[j] + arr[k] = S or where they were only checking whether one such triplet exists.

My question is to find out all i,j,k in arr[] such that arr[i] + arr[j] + arr[k] <= S

score 5 · Accepted Answer

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

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

然后，在你拿起arr[i]和arr[j]where之后i < j，你可以S - arr[i] - arr[j]在剩下的array[j+1...n]. 对 index 进行二进制搜索后m，k可能位于j+1和之间m。

我认为这可能会降低复杂性。你怎么看？

score 5 · Accepted Answer

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

例如，让数组是数字 1 到n。让S = 3n. 显然，三个数组元素的任何子集都会小于S并且存在(n choose 3) = O(n³)子集。

不过，有几种方法可以加快非最坏情况的速度。例如，先尝试对数组进行排序。那应该给你一些提示。

score 0 · Accepted Answer

这会有什么复杂性？

如果应用于排序列表（升序），只需逐个f列出总和小于或等于的三元组，而不会创建重复项或扫描过第一个太大的元素。s

哈斯克尔代码：

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]]

score 0 · Accepted Answer

我将原始答案保留在下面，但这实际上可以在 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 ² ) 中解决问题。不过，您应该事先对数组进行排序。

本质上，我只是通过在剩余索引 (k) 中搜索小于或等于 x（或您的情况下为 S）的所有总和来找到所有可能的三元组，其中第一个索引 i 为零，下一个索引为 j。之后，我将 j 增加 1 并重复该过程。一旦 j 到达数组的末尾，我就开始这个过程，我的 i 现在是 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

score 0 · Accepted Answer

这可以在 O(n ² ) 复杂度中解决。

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

现在从前面开始，一次固定一个数字。现在问题减少到在排序数组中找到 2 个数字，其总和 <= 给定总和。使用 2 个指针，一个从开始，一个从结束，这可以在 O(n) 中解决。所以整体复杂度是 O(n ² )

algorithm - Find all triplets in array with sum less than or equal to given sum

5 回答 5

Related

Reference