arrays - 找到一个子数组，其中每对的总和大于给定的 K

Question

我得到了一个整数数组 A。现在我必须找到一个子数组(原始数组的子序列)，其中每对的总和大于或等于预定义的 K。

我的想法:-

• 将根据数组中值的范围在 O​​(nlgn) 或 O(n) 中对数组进行排序。
• 找出排序数组中的 i 使得 sorted[i] + sorted[i+1]>=k
• 将最大值设置为sorted[i]
• 遍历原数组，删除所有小于max的值，即要求的子序列

对数组的所有元素重复上述操作。

运行时间:- O(nlgn)

解决方案是最优的吗？我们可以进一步改进它吗？

例子:-

-10 -100 5 2 4 7 10 23 81 5 25

排序数组

-100 -10 2 4 5 5 7 10 23 25 81

让 K = 20

子数组:-

10 23 25 81

如果问题是找出最长的子数组，alestanis 在答案中建议的算法就可以正常工作:)

Answer 1

这是一个相当简单的解决方案。

>>> def f(A, k):
...     solution = [item for item in A if 2*item >= k]
...     m = min(solution)
...     for item in A:
...         if item + m >= k and 2*item < k:
...             solution.append(item)
...             break
...     return solution
...
>>> f([-10, -100, 5, 2, 4, 7, 10, 23, 81, 5, 25], 20)
[10, 23, 81, 25]
>>>