algorithm - 计算符合 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

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

获取数组和k您陈述的值(value)观:

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

对数组进行排序将产生:

a_sort = [2,4,5,7]

现在我们可以考虑以下过程:

1. 设置 ii = 0, jj = 1

2. 选择 a_sort[ii]作为你子集的一部分

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

3. 添加 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步

根据您的输入，此过程应返回:

[[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` 因为 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