arrays - 数组搜索的伪代码

Question

问题：

“编写一个算法，给定一个数组 A 和一个整数值 k，如果 A 中有两个不同的整数之和为 k，它返回值 true，否则返回 false。”

我的伪代码：

输入：大小为 n 且值为 k 的数组 A

输出：如果 A 中的两个不同整数等于 k，则为 true，否则为 false

Algorithm ArraySum(A, n, k)
for (i=0, i<n, i++)
    for (j=i+1, j<n, j++)
        if (A[i]+A[j]=k)
            return true
return false

我是否正确编写了此算法？有没有我没有看到的错误？

score 2 · Accepted Answer

关于这个问题，我有两种解决方案

第一个解决方案

1.制作一个空哈希
2.在哈希中标记数组中的所有数字

 for each i (Array A){
        hash[i] = 1;
    }

3.只需运行一个O(n)循环

for each i (Array A)
    if(  hash[ k - i ] ) 
        print "solution i and k-i"

这会给你带来O(n)复杂性

第二种解决方案

1.排序数组
2.在排序后的数组上运行一个O(n)循环

for each i (Array A)
    binary_search( Array, k - i); [log n operation]

这会给你带来O(n logn)复杂性。

score 0 · Accepted Answer

这看起来像是背包问题的一些案例。

对于您的情况（只有两个数字），对数组进行排序以减少比较次数（A[i]+A[j]=k）可能会更好。

例如：

you have sorted array [1 3 5 8 10 12 14 20 50 60 100]
sum of two numbers must be equal to 30

然后你可以写

 while(a[i] <= 30) {
   while(a[i] + a[j] <= 30) {
    // ...
    i++;
    j++;
   } 
 }

score 0 · Accepted Answer

如果两个不同的整数表示A[i], A[j]wherei != j而不是A[i] != A[j]，则您的伪代码是正确的。

3 回答 3