Два указателя для подсчёта пар с разностью меньше D в отсортированном массиве
Дан массив, нужно посчитать число пар (i, j), i < j, у которых a[j] - a[i] < D. Наивно O(n^2). Знаю, что после сортировки можно за O(n) двумя указателями, но не уверен, как именно двигать и не посчитать ли пары дважды.
2 ответа
Сортируем массив (O(n log n)), дальше два указателя за O(n). Идея: для правого указателя r найдём самый левый l, при котором a[r] - a[l] < D. Тогда все пары (l, r), (l+1, r), ..., (r-1, r) годятся, их r - l. Суммируем по всем r — каждая пара считается ровно один раз (правый элемент фиксирован как r).
Левый указатель монотонно растёт: при увеличении r левая граница окна может только сдвигаться вправо (массив отсортирован), так что суммарно l пройдёт массив один раз.
long long countPairs(vector<int> a, int D) {
sort(a.begin(), a.end());
long long cnt = 0;
int l = 0;
for (int r = 0; r < (int)a.size(); r++) {
while (a[r] - a[l] >= D) l++; // сдвигаем левую границу, пока окно невалидно
cnt += (r - l); // пары (l..r-1, r) — все с правым концом r
}
return cnt;
}
Сложность O(n log n) (доминирует сортировка), память O(1) сверх массива. cnt может быть до n*(n-1)/2 ≈ 5e9 → обязательно long long.
Почему не считаем дважды: мы перебираем каждую пару по её большему элементу r и берём только меньшие индексы из окна. Никакая пара не имеет двух «больших» концов, так что двойного счёта нет. Это типичный приём «фиксируем правый, считаем левые».
Альтернатива без явных двух указателей — upper_bound: для каждого r число подходящих левых = lower_bound(a, a[r] - D + 1) ... r, то есть индекс первого элемента >= a[r] - D + 1 (если разность строго < D, нам нужны a[l] > a[r] - D). Это O(n log n) тоже, но чуть медленнее из-за логарифма на каждый элемент и легче ошибиться со строгостью неравенства (< D против <= D). Два указателя чище и без логарифма. Главное — определись со строгостью: a[r]-a[l] < D vs <= D меняет условие в while на >= vs >.