如何找出任意两个元素和> k的子数组？

Question

上周末我在一次采访中被问到这个问题。有一个正数数组。从这个数组中，您需要找出子集。从这个子集中，您应该能够挑选出任意两个数字，并且它们的总和将始终大于 k。 k是用户输入的值。

我分两步解决了这个问题。在第一遍中，我将拾取所有大于 k 的项目并将它们放入子数组中。在这样做的同时，我会从这个子集中找出最小值。

在下一遍中，我将按降序对数组进行排序。之后，我将继续向子集中添加数字，方法是将它们与子集中的最小数字相加。

上面提到的解决方案解决了问题。但是时间复杂度为 O(n + nlogn)。但是面试官希望它是 O(n)。不用说我无法做到这一点。请帮我算法。我确实尝试搜索互联网。但是我找不到任何时间复杂度为 o(n) 的东西。

Answer 1

是的，可以用复杂度 O(n) 来解决它。使用数组上的单个循环，只取大于 k/2 的数字。一个简单的算法如下所示：

for(int i=0; i<n; i++){
    if(arr[i] > k/2.0){
         add arr[i] to the subset
    }
}

Answer 2

这在 O(n).

中运行

这里的推理如下：

任何 2 个元素 > k/2 加起来将超过 k。
如果一个元素是<= k/2，另一个元素需要是> k/2才能加起来至少k，所以元素不能超过一个<= k/2（因为如果有 2 个，那 2 个加起来不会超过 k）。

一个例子是 k = 10, array = [3,4,8,9,10]，输出是 [3,8,9,10] 或 [4,8,9,10]。 8,9,10 将在第一步中添加，然后我们将在第二步中添加 3 或 4。

技术说明：“子集”表示独特的元素。我们可以使用散列 table 来获得预期（但不保证）O(n) 复杂度。如果它是一个“子序列”（不是唯一元素），我们可以将它们添加到一个数组或链表中以获得 O(n) 的复杂性。

How to find out the sub array where any two elements sum > k?