查找数组总和所有三胞胎小于或等于给定的总和 [英] Find all triplets in array with sum less than or equal to given sum

问题描述

这是最近要求在接受采访时的朋友，我们不知道的比简单的为O（n ³ ）之一。

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?

的问题是找到所有三胞胎在一个整数数组，其总和小于或等于给定的合计值S

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

注：我看到的SO具有性能为O（n ² log n）的，但所有的人都解决这一问题的更简单的版本类似，其中改编等这样的问题[我] +改编[J] +改编[K] = 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.

我的问题是找出所有 I，J，K 在改编[] ，使得改编[I] +常用3 [J] +改编[K]＆LT; = S

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

推荐答案

我有一个想法，但我不知道它是否工作。

I have an idea, but I'm not sure if it works.

preprocess（删除元素> 取值）和数组第一个排序。

Preprocess (remove elements > S) and sort the array first.

然后，拿起后改编[I] 和改编[J] ，其中 I＆LT; Ĵ，您可以二进制搜索的S - 常用3 [I] - 在剩下的改编[J] 阵列[J + 1 ... N] 。一旦你二进制搜索的指数 M 的 K J + 1之间可能在于和 M 。

Then, after you picking up arr[i] and arr[j] where i < j, you may binary search S - arr[i] - arr[j] in the remaining array[j+1...n]. Once you binary-searched the index m, the k could lie between j+1 and m.

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

I think this may reduce the complexity. What do you think?

这篇关于查找数组总和所有三胞胎小于或等于给定的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！