Найти все отличия в массиве за O(n)

Вопрос: Дано отсортированный массив A найдите все возможные разности элементов из A.

Мое решение:

for (int i=0; i

Конечно, это O(n^2), но я вообще ничего не пересчитываю. Я поискал в интернете и нашел вот это: http://www.careercup.com/question?id=9111881. Там написано, что лучше нельзя, но на собеседовании мне сказали, что можно сделать O(n). Что правильно?