计算符合 min(subset)+max(subset) < k 的数组子集

Question

在面试中被问到这个问题，没有比生成所有可能的子集更好的答案了。示例：

a = [4,2,5,7] k = 8

output = 4

[2],[4,2],[2,5],[4,2,5]

面试官试图暗示对数组进行排序应该会有帮助，但我仍然想不出比蛮力更好的解决方案。将感谢您的意见。

Answer 1

对数组进行排序
对于索引 l 处的元素 x，对数组进行二进制搜索以获取数组中最大整数的索引，即 < k-x。让索引为 r.
对于 min(subset) = x 的所有子集，我们可以有索引在 (l,r] 范围内的任何元素。具有 min(subset) = x 的子集数成为 (r-l) 元素的可能子集总数，因此计数 = 2^(r-l)（或 0 如果 r<l）。
（注意：在所有此类子集中，我们正在修复 x。这就是 (l,r] 范围不包含 l 的原因）
您必须遍历数组，对每个 element/index 使用上述过程来获取当前元素最小且子集满足给定约束的子集的计数。如果您找到带有 count=0 的元素，则中断迭代。

这应该具有 0(N*log(N)) 的复杂性，对于面试问题来说已经足够好了。

对于给定的示例，排序数组 = [2,4,5,7].

对于元素 2、l=0 和 r=2。计数 = 2^(2-0) = 4（涵盖 [2],[4,2],[2,5],[4,2,5]
对于元素 4、l=1 和 r=0。计数 = 0，我们打破迭代。

Answer 2

面试官暗示对数组进行排序会有所帮助，而且确实有帮助。我会尽力解释。

采用数组和 k 您陈述的值：

a = [4,2,5,7]
k = 8

对数组进行排序将得到：

a_sort = [2,4,5,7]

现在我们可以考虑以下程序：

设置 ii = 0, jj = 1
选择 a_sort[ii] 作为您子集的一部分

2.1。如果 2 * a_sort[ii] >= k，你就完成了。否则，子集 [a_sort[ii]] 满足条件并且是解决方案的一部分。
将 a_sort[ii+jj] 添加到您的子集

3.1。如果a_sort[ii] + a_sort[ii+jj] < k,

3.1.1。子集 [a_sort[ii], a_sort[ii+jj]] 满足条件并且是解决方案的一部分，以及由任何额外数量的元素组成的任何子集 a_sort[kk] 其中 ii< kk < ii+jj

3.1.2。设置 jj += 1 并返回步骤 3。

3.2。否则，set ii += 1、jj = ii + 1，返回步骤 2

根据您的输入，此过程应该 return:

[[2], [2,4],[2,5],[2,4,5]]
# [2,7] results in 9 > 8 and therefore you move to [4]
# Note that for [4] subset you get 8 = 8 which is not smaller than 8, we are done

解释

如果 [a_sort[ii]] 的子集不包含 2 * a_sort[ii] < k，向该子集添加额外的数字只会产生 min(subset)+max(subset) > 2 * a_sort[ii] > k and therefore there will not be any additional subsets which hold the wanted condition. Moreover, by setting a subset of [a_sort[ii+1]] will results in 2 * a_sort[ii+1] >= 2 * a_sort[ii] > k` sinse a_sort 已排序。因此，您不会找到任何其他子集。
对于 jj > ii，如果 a_sort[ii] + a_sort[ii+jj] < k 那么你可以将 a_sort 中的任何成员推入子集，只要索引 kk 大于 ii 和低于 ii+jj 因为 a_sort 是排序的，将这些成员添加到子集不会改变 min(subset)+max(subset) 的值，它将保持 a_sort[ii] + a_sort[ii+jj] 我们已经知道这个值更小谢谢 k

获取计数

如果您只是想要可能的子集，这比自己生成子集更容易。

假设 ii > jj 条件成立，即 a_sort[ii] + a_sort[ii+jj] < k。如果 jj = ii + 1 则增加 1 个可能的子集。如果 jj > ii + 1 有 jj - ii - 1 个附加元素，这些元素要么存在，要么不改变值 a_sort[ii] + a_sort[ii+jj]。因此，总共有 2**(jj-ii-1) 个附加子集可用于添加到解决方案组（jj-ii-1 个元素，每个元素都独立存在或不存在）。这也适用于 jj = ii + 1 因为在这种情况下 2**(jj-ii-1) = 2**0 = 1

看上面的例子：

[2] 加 1 个计数
[2,4] 加 1 个计数 (1 = 0 + 1)
[2,5] 添加 2 个计数 (2 = 0 + 2 --> 2 **(2 - 0 - 1) = 2**1 = 2)

总计 4

计算符合 min(subset)+max(subset) < k 的数组子集

Count subsets of array which qualify min(subset)+max(subset) < k

algorithm

解释

获取计数