0

我有一个在文本文件中生成值的系统，其中包含如下值

第 1 行：可能的总值

第 2 行：数组中的元素数量

第 3 行（如果需要，额外的行）：数字本身

我现在正在考虑一种方法，我可以从数组中的第一个整数中减去总值，然后在数组中搜索余数，然后做同样的事情直到找到对。

另一种方法是在排列组合的基础上将数组中的两个整数相加并找到对。

根据我的分析，第一个解决方案更好，因为它减少了迭代次数。我的分析在这里是否正确，还有其他更好的方法吗？

编辑：我将在这里给出一个示例以使其更清楚第 1 行：200 第 2 行 = 10 第 3 行：10 20 80 78 19 25 198 120 12 65

现在这里的有效对是 80,120，因为它总和为 200（在第一行中表示为输入文件中可能的总值）并且它们在数组中的位置将是 3,8。所以找到这对我列出了我的方法在哪里我取第一个元素，然后用可能的 Total 值减去它，然后通过基本搜索算法搜索另一个元素。

使用此处的示例，我首先取 10 并用 200 减去它得到 190，然后搜索 190，如果找到则找到该对，否则继续相同的过程。

4

2 回答 2

3

您的问题含糊不清，但是如果您要在数组中查找总和为某个数字的对，则可以O(n)使用哈希表平均完成。

迭代数组，并为每个元素：
(1) 检查它是否在表中。如果是 - 停止并返回有这样一对。
(2) Else：插入num-element到哈希表中。

如果您的迭代在没有找到匹配项的情况下终止 - 没有这样的对。

伪代码：

checkIfPairExists(arr,num):
   set <- new empty hash set
   for each element in arr:
        if set.contains(element):
            return true
         else:
            set.add(num-element)
    return false

“是否存在总和为某个数的子集”的一般问题是NP-Hard，并且被称为子集和问题，因此没有已知的多项式解决方案。

于 2012-11-14T11:52:34.540 回答
1

如果您试图找到一对 (2) 数字总和为第三个数字，通常您会得到类似的结果：

for(i=0;i<N;i++)
   for(j=i+1;j<N;j++)
      if(numbers[i]+numbers[j]==result)
         The answer is <i,j>
         end

这是O（n ^ 2）。但是，可以做得更好。

如果数字列表已排序（需要 O(n log n) 时间），那么您可以尝试：

for(i=0;i<N;i++)
   binary_search 'numbers[i+1:N]' for result-numbers[i]
   if search succeeds:
      The answer is <i, search_result_index>
      end

也就是说，您可以逐步遍历每个数字，然后在剩余的列表中进行二进制搜索以查找其伴随数字。这需要 O(n log n) 时间。您可能需要自己实现search上面的函数，因为内置函数可能只是在 O(n) 时间内遍历列表，导致 O(n^2) 结果。

对于这两种方法，您都需要检查当前数字是否等于您的结果的特殊情况。

两种算法使用的空间都不会超过数组本身占用的空间。

为编码风格道歉，我对 Java 不是很熟悉，这里的想法很重要。

于 2012-11-14T11:52:19.393 回答