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。
...

Answer 2

尝试这个：

由于数组已排序，因此取第一个元素 (arr[0]) 和最后一个元素 (arr[8]) 的总和。如果总和大于 12，那么我们需要降低总和，因此我们将最大的数字替换为下一个最大的数字（在本例中为 arr[7]）；如果总和小于 12，我们需要增加总和，因此我们将最小的数字替换为下一个最小的数字，（在这种情况下，将 arr[0] 替换为 arr[1]）。不断重复这个过程，直到你得到你想要的总和，或者你求和的两个数字来自数组中的同一个索引。