arrays - 排序数组并找到复杂度为 O(n) 的总和

Question

我们已经对数组 arr[]={2,4,5,7,8,12,16,18,20} 进行了排序。

我们需要找出加法为12的元素对，复杂度为O(n)。

有人可以帮忙吗？

Answer 1

不幸的是，没有适合您的解决方案，只有一些需要考虑的事情应该会引导您朝着正确的方向前进:

记住数组是有序的，下列哪项是正确的？

   arr[x+1] + arr[y] < arr[x] + arr[y]
or arr[x+1] + arr[y] > arr[x] + arr[y]

   arr[x] + arr[y-1] < arr[x] + arr[y]
or arr[x] + arr[y-1] > arr[x] + arr[y]

如果您思考这些问题的答案足够长(并且可能画出来)，那么应该会有一个解决方案。

关于如何开始的提示:

设 x = 0，y = n-1。
...