寻找一个子数组，使得其中每一对元素的和都大于给定的K

Question

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

我的想法是：

- 将数组按照值的范围排序为O(nlgn)或O(n)。 - 找到排序后的数组中的i，使得sorted[i] + sorted[i+1]>=k。 - 将max设置为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在答案中提出的算法将很好地工作 :)

- Prashant Singh

---

@raina77ow 示例已添加 - Prashant Singh

你的截止点应该是10，子数组应该是10，...，81。 - Eduardo

我认为，在对数组进行排序后，在第二步中，您需要找到最小的索引i，使得array[i] + array[i+1] >= K。 - Eduardo

对我来说，“子数组”这个术语意味着对数组进行排序会破坏解决方案。也许你正在寻找数组中元素的子集。任何子集都可以吗？还是需要最大的、第一个的、最小的或其他什么类型的子集？每种情况都是一个有很大不同的问题... - twalberg

我赞同那些评论。但我不理解你提供的子数组为什么合适；一开始我认为每个相反元素的总和应该不少于K，但是5+10打破了这个规则... - raina77ow

Answer 1

这里提供一种略有不同的方法，与早期评论中的提示类似，并且与alestanis的答案略有不同，因为它不依赖于数组拆分。 它通过数组进行单次遍历（尽管这并不能保证O（N）），只需要跟踪两个最小值以及正在考虑的子序列的起始和结束点。

对于连续子序列，所有可能的对之和都必须等于20，则两个最小元素的总和必须> = 20。 因此，从考虑相邻的元素对开始（array [0]和array [1]）。 如果它们的总和不到20，那么继续移动到array [1]和array [2]。 如果它们的总和达到20或更多，则将右端点扩展一位。如果新元素大于其他两个元素，则它将与任何已经在子序列中的元素相加总和为20或更大，然后可以再次扩展右端点。 如果它较小，则需要使用一些比较选择两个最小元素，如果两个新的最小元素现在不能总和为20或更多，则从子序列中删除刚添加的元素，并注意特定的子序列，然后重新开始使用现有子序列的第二个和第三个元素。 最后，您通常会有符合约束条件的子序列列表，很容易选择第一个或最大的或您需要的任何内容。

例如，使用您列出的序列：

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

从-10, -100开始。它们的总和不是20，所以向右移动一个到-100, 5。同样，这些也不是20，所以继续往下找。第一对总和为20的是10, 23。现在，我们将范围扩大到10, 23, 81。81比两个最小值都要大，所以我们需要再扩大一次范围，得到10, 23, 81, 5。5比10和23都小，所以新的最小值是5和10，它们的总和不是20，因此添加5是错误的，我们需要回溯。我们发现10, 23, 81就是一个符合条件的子序列。接下来，我们继续处理23, 81，这会导致我们找到子序列23, 81, 5, 25，这也符合条件。

因此，最终我们有四个可能的子序列符合条件- 10, 23, 81，23, 81, 5, 25，81, 5, 25和5, 25。后面两个可以通过在包含原始列表最后一个元素的解决方案之后停止寻找额外的解决方案来被剪枝，这将留下前两个可能性。从这里，我们可以选择第一个或最长的一个。

- twalberg

---

这个解决方案的复杂度可能太高了。 - Kshitij Jain

Answer 2

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

>>> 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]
>>>

- Rusty Rob

---

不错的解决方案。顺便问一下，“2*item>=k”是怎么出现的？逻辑是什么？ - Prashant Singh

f([1, 2], 3)怎么样？正确的输出应该是[1, 2]，但是你的算法会输出[1]。 - undefined

它会给出[1,2]。@prashant解决方案中只能有一个小于k一半的项目。 - Rusty Rob

您的解决方案将给出数组中所有整数的列表，其中任何两个数字的和都大于或等于给定的k，并且该列表可能不是一个子序列。 - ravi

看看注释的澄清，我认为他只想要数组中的数字。这就是他要求的。他误用了“子序列”和“子数组”这个词。那不是他想要的。 - Rusty Rob

Answer 3

首先，您不能对集合进行排序。我认为问题的一部分是找到作为输入给出的原始数组的子数组。

这可以通过递归来解决：

1. 找到数组中的两个最小值， m1 和m2 2. 如果 m1 + m2 < K 则将数组分成至多两个较小的不同时包含 m1 和 m2 的数组。如果 m1 和 m2 的索引是 i 和 j 且 i<j，则子数组为 [O, j-1] 和 [i+1, n]。然后重复步骤 1。 3. 如果 m1 + m2 >= K 则当前的数组是您问题的可行解：返回其长度。 4. 添加一些剪枝以丢弃无用的数组。

让我们在您的示例上应用此方法：

Initialize max = 0;
A1 = -10* -100* 5 2 4 7 10 23 81 5 25

这个数组的最小值是-10和-100。以这些值为分界点将数组拆分，这样我们只得到一个数组（很走运！）

A2 = 5 2* 4* 7 10 23 81 5 25

A2的两个最小值分别为2和4。我们将其拆分为：

A3_1 = 5* 4*   and    A3_2 = 2* 7 10 23 81 5* 25

这将继续进行以下迭代：

A3_1 discarded    
A3_2 becomes A4_1 = 2* 7* 10 23 81    A4_2 = 7* 10 23 81 5* 25

A5_1 = 7* 10* 23 81
A5_2 = 7* 10* 23 81        -> Duplicate, discarded
A5_3 = 10* 23 81 5* 25

A6_1 = 10* 23* 81          -> Yay! update max = 3
A6_2 = 10* 23* 81          -> Length <= max. Discarded
A6_3 = 23 81 5* 25         -> Yay! update max = 4

在这个例子中，我通过以下方式剪枝了搜索空间：

• 消除重复的子集（例如可以通过将它们存储在一个集合中来完成）
• 丢弃长度小于或等于当前已知最大长度的子数组

该算法的复杂度为：

• 平均情况下是O(nlogn)，
• 最坏情况下是O(n^2)。当数组已排序且最小值始终在数组的一侧时，会发生这种情况，因此无法将数组拆分为较小的子数组（例如示例的第一次迭代）。

- alestanis

---

你说的无法排序是什么意思？是指数字的顺序很重要吗？ - Prashant Singh

如果你进行排序，那么你找到的子数组并不是原始数组的子数组。它们只是你原始数组中随机放置元素的集合。在你的例子中，子数组10 23 25 81 并不属于原始数组。 - alestanis

我不明白你是如何在每一步中分割数组的。 - Prashant Singh

我已经编辑了我的问题。它总是以O(nlogn)的时间运行。顺便说一下，我没有投票反对！ - Prashant Singh

@robertking，原始问题是关于子数组的。问题后来进行了编辑（但请看未更改的标题） :) - alestanis

Answer 4

void sub_array(int ar[],int n,int val)
{
    int max=0;
    for(int i=0;i<n;i++)
    {
        if(ar[max]<ar[i])
            max=i;
    }
    int b[n];
    max=ar[max];
    int p=0;
    int min=0;
    for(int i=0;i<n;i++)
    {
        if(ar[i]+max>val)
        {
            b[p]=ar[i];
            if(ar[i]<max)
            {   
                min=p;
                max=ar[i];
            }
            p++;
        }
        else
        {
            if(ar[i]>max)
            {
                max=ar[i];
                b[min]=ar[i];
            }
        }
    }
    for(int i=0;i<p;i++)
    {
        cout<<b[i]<< "  " ;
    }
}

- user3019608