java - 在数组中搜索值的总和

Question

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

Line 1 : Total value possible

Line 2 : No of elements in the array

Line 3(extra lines if required) : The numbers themselves

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

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

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

编辑:我将在此处提供示例以使其更清楚第 1 行:200第 2 行=10第 3 行:10 20 80 78 19 25 198 120 12 65

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

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

Answer 1

你的问题是模糊的，但如果你在数组中寻找一对总和为某个数字的对，使用哈希表平均可以在 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 ，并被称为 subset-sum problem , 所以它没有已知的多项式解。