Возможно ли перейти от O(N²) к O(N Log N) или, может быть, к O(N)? Код C# – проблема/решение [закрыто] ⇐ C#

[Anonymous]

введите здесь описание изображения
Решение достаточно простое, но я не могу придумать ничего большего, чтобы его оптимизировать. Я имею в виду, возможно ли это сделать при O(nlogn) или даже O(n)?
Я даже пробовал LINQ на C#. Тем не менее время превышено. Таким образом, это должно быть O(n²), которое проверяется, поскольку дает правильный ответ.

Код: Выделить всё

int count = arr
.SelectMany(n => arr,(a,b) => new {a,b})
.Where(pair => pair.a - pair.b == 2)
.Count();

Я пытался решить эту задачу 3 раза, но все попытки не увенчались успехом из-за превышения времени. Я сдаюсь. Я не могу придумать больше решения. Лучше всего было бы разделить n² на 1/2.
Было бы неплохо объяснить другой алгоритм, желательно тот, который намного быстрее моего. Если вы хотите показать это в коде, используйте C#, но я могу читать только C/C++

Подробнее здесь: https://stackoverflow.com/questions/788 ... c-sharp-co