未排序数组的双元素求和搜索

Question

我正在学习算法简介，在那里我遇到了ex2.3-7。

经过深思熟虑，我意识到暴力算法需要O(nlogn(：

bool exactSum(int arr[], const int &length, const int &value) {
bool isExact = false;
for(unsigned i = 0; i < length - 1; ++i) {
for(unsigned j = i + 1; j < length; ++j) {
if(arr[i] + arr[j] == value) {
isExact = true;
break;
}
}
}
return isExact;
}

你看，只有nlogn检查。我错了吗？

Answer 1

您描述的算法需要O(n^2(的时间复杂性，因为在最坏的情况下，有n*(n-1(/2个比较。

所有功劳都归功于@Shridhar R Kulkarni，他指出，即使不进行排序，这个问题也可以解决。

在这种情况下，您将需要使用哈希映射将数组的元素及其各自的计数存储在hashmap中现在，迭代数组元素。假设您位于索引i。只需检查哈希映射中是否存在(value - are[i])即可。

时间复杂度=O(n(。

特殊情况

当arr[i]等于value - arr[i]时，检查元素arr[i]的计数是否大于1以使一对存在。

特殊情况下的学分-@Dillon Davis。

Answer 2

@Deepak发布的回答对于这篇文章来说已经足够好了。但是，您可以简化更多。字典方法对a+b=value和a=b的情况进行两次迭代和额外的条件处理。相反，您可以通过使用无序集在一次迭代中完成它，而且实际上空间更小。

Psuedocode:

for element in array:
if value - element in unordered_set:
return true
unordered_set.add(element)
return false
Time complexity: O(n)
Space complexity: O(n)

使用与上面相同的逻辑，您可以使dictionary/hashmap与单个迭代一起工作，以避免额外的迭代来获取计数。