algorithm - x+yz 在 -1 和 1 之间

Question

让是范围内不同整数[a_1 a_2 ... a_n]的列表。给出一个算法，如果存在三个不同的元素，例如 ，则返回，否则返回。[1,10n]truex,y,z-1 <= x+y-z <= 1false

蛮力算法（检查所有可能的组合x+y-z，及时运行O(n^3)。有更有效的算法吗？

Answer 1

就在这里。这是使用额外空间的O(n^2)最坏情况算法。O(n)

这个想法是检查所有可能的对（而不是三元组），并迭代地标记您已经看到的元素，并将每对的总和与它们进行比较。
对于每一对，检查它的总和是否有匹配的元素，该元素恰好是总和 ( x+y-z == 0) 或者如果添加 1 ( ) 可以得到的元素，x+y+1-z == 0 -> x+y-z = -1或者如果减少 1 ( x+y-1-z == 0 -> x + y - z == 1)可以得到的元素

伪代码：

mark = new boolean[10n]; //all initialized to false
sort arr //O(nlogn)
for each i in n,1: (reverse order)
   for each j in 1,i-1:
      //neglected range check, make sure it is done
      if (mark[arr[i]+arr[j]] || mark[arr[i]+arr[j]+1] || mark[arr[i]+arr[j]-1]):
          return true
      mark[arr[i]] = true
return false

请注意，我们i从n1 迭代，因为z > x和z > y- 我们要确保我们正在检查所有与已经在列表中的元素的对（如果它存在）

正确性证明：
如果有一个解决方案x+y-z = 0- 那么z > x和z > y（所有元素都是正的不同整数）。
不失一般性，我们假设x > y。所以，当arr[i]=x在外循环中迭代时，会有一些j<i这样的arr[j]=y. 另外，因为z>x-mark[z] == true因为我们在之前迭代它时标记了它。
因此：该算法将找到mark[arr[x] + arr[y]] == true，并产生true。 案件
的类似证明。+-1

如果算法结果为真，那么它发现条件之一为真。让我们假设它是mark[arr[i] + arr[j]]（其他情况的证明将是相似的）。
所以，我们发现了mark[arr[i] + arr[j]] == true——所以我们插入了它，因为有一些z这样z = arr[i] + arr[j]的元素，并且算法对于这种情况是正确的。