Задача с собеседования в Josh Technology Group

Дан целочисленный массив nums, индексированный с нуля, длины n и целое число target. Верните количество пар (i, j), где 0 <= i < j < n и nums[i] + nums[j] < target.

Пример 1:
Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: Существует 3 пары индексов, удовлетворяющих условию:
- (0, 1), так как 0 < 1 и nums[0] + nums[1] = 0 < target
- (0, 2), так как 0 < 2 и nums[0] + nums[2] = 1 < target
- (0, 4), так как 0 < 4 и nums[0] + nums[4] = 0 < target
Обратите внимание, что пара (0, 3) не учитывается, так как сумма nums[0] и nums[3] не является строго меньшей target.

Пример 2:
Input: nums = [-6,2,5,-2,-7,-1,3], target = -2
Output: 10
Explanation: Существует 10 пар индексов, удовлетворяющих условию:
- (0, 1), так как 0 < 1 и nums[0] + nums[1] = -4 < target
- (0, 3), так как 0 < 3 и nums[0] + nums[3] = -8 < target
- (0, 4), так как 0 < 4 и nums[0] + nums[4] = -13 < target
- (0, 5), так как 0 < 5 и nums[0] + nums[5] = -7 < target
- (0, 6), так как 0 < 6 и nums[0] + nums[6] = -3 < target
- (1, 4), так как 1 < 4 и nums[1] + nums[4] = -5 < target
- (3, 4), так как 3 < 4 и nums[3] + nums[4] = -9 < target
- (3, 5), так как 3 < 5 и nums[3] + nums[5] = -3 < target
- (4, 5), так как 4 < 5 и nums[4] + nums[5] = -8 < target
- (4, 6), так как 4 < 6 и nums[4] + nums[6] = -4 < target

Ограничения:
1 <= nums.length == n <= 50
-50 <= nums[i], target <= 50

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
При наивном решении мы бы проходили по вложенному циклу за O(n²).
Но в данном случае заметим, что для удовлетворения условию nums[i] + nums[j] < target важны не позиции эл-в в массиве, а только их значения => мы можем отсортировать массив в восходящем порядке, и для каждого текущего nums[i] все подходящие nums[j] будут идти подряд от начала до некоторого индекса (образовывать префикс), так как если nums[i] + nums[j] < target, то nums[i] + nums[k] < target для любого k < j.

Логично использовать алгоритм двух указателей и двигать указатели навстречу друг другу, проверяя сумму nums[left] и nums[right]. К count (счетчик пар) добавляется не одна пара, а целая группа пар (count += right - left), так как nums[left] - самый маленький текущий эл-т, и, если его сумма с самым большим текущим эл-м (nums[right]) меньше target => сумма nums[left] и любого эл-та между left и right будет также меньше target.

Переменные:
left - индекс первого эл-та в массиве;
right - индекс последнего эл-та;
count - счётчик пар, удовлетворяющих условию.

Пока left меньше right, проходим по массиву, сужая окно между указателями:
Сравниваем сумму текущей пары эл-в с target:
Если меньше:
- добавляем к count значение right - left. Таким образом, все пары с текущим left учтены;
- сдвигаем left вправо.
Если сумма больше или равна target:
- сдвигаем right влево.

В конце возвращаем count.

Сложность
O(n log n) - по времени (сортируем массив, где n - кол-во элементов в массиве; обход двумя указателями - за O(n), так как проходимся по каждому элементу единожды)
O(n) - по памяти (для сортировки на питоне)

Код
class Solution:
def countPairs(self, nums: List[int], target: int) -> int:
nums.sort()
count = 0
left = 0
right = len(nums) - 1

while left < right:
if nums[left] + nums[right] < target:
count += right - left
left += 1
else:
right -= 1

return count

@algoses