算法-给定一个由n个整数和另一个整数x组成的集合S，确定S中是否存在两个和正好为x的元素

Question

描述一个算法，其中给定一组由n个整数和另一个整数x组成的S，确定S中是否存在两个元素，其和正好是x。请告诉我我的算法是否正确，或者我需要做什么修改？算法：

Algo(i,j,k,S)
    for (j = 1 to S.length - 1 , i++ )
       for (i= j+1 to S.length)
        A[k] = A[j] + A[i]
        if A[k] = x
          return A[i], A[j]
        else j++

Answer 1

我想你需要一些标准：

1） 在任何一行之前添加一个数字，以便将来方便地引用它们
2）使用语句格式时，请保留该格式：

 for (j = 1   to S.length - 1 , i++ )
 for (i = j+1 to S.length     , ??? )

3）当你需要一些变量时，在某处声明all：A[]， k.

嗯，这可能是一个更好的：

0) Start [Algo(i, j, S[], x)] 'i, j are local & S[], x are inputs
1) for (j = 1 to S.length - 1, j++ )
1.1) for (i = j + 1 to S.length, i++ )
1.1.1) if (x = S[j] + S[i])
1.1.1.1) return 'at least one match', S[i], s[j]
2) return 'No match'
3) End

Answer 2

O（n）平均时间，如果数组较大且有许多解决方案，则更快：从包含第一个数组元素a[0]的集合开始。然后，对于i=1到（元素数量-1），检查x-A[i]是否在集合中，如果在集合中，则退出，然后向集合中添加[i]。

对于具有k个解的随机数组，这将是O（N*min（1,1/sqrt（k））。感谢Amit首先提出的集合。

如果我们正在寻找多个值x，我们将利用这样一个事实，即我们已经向集合中添加了许多值。如果我们没有找到一个x的解，然后另一个x有k个解，那么对于那个x，我们将降至O（N/k）。

Answer 3

你的算法和你的算法有点小问题-

• k从何而来？...的索引？
• 什么是x？缺少作为参数
• 为什么i和j是参数？
• 为什么在i的循环中增加j而在j的循环中增加i？
• 您似乎也在修改数组，这将产生错误的结果

应该对它进行修改，以解决这些问题，例如：

Algo(S,x)
    for (i = 1 to S.length - 1 , i++ )
       for (j= i+1 to S.length)
        t = S[j] + S[i]
        if t = x
          return S[i], S[j]
        else j++

除此之外，你的算法似乎是正确的，方法基本上是一种蛮力——你检查所有对，所以如果存在这样的对，你肯定会找到它。然而，您的方法效率很低，它在O（n^2）时间内运行。

这个问题可以用更有效的方法解决：

1. O（nlogn）time（和少量额外空间），通过排序和迭代数组，对每个元素x进行迭代，同时对S-x进行二进制搜索，如果找到，答案就是这些元素