Leetcode: 2824. Count Pairs Whose Sum is Less than Target

Ссылка на задачу: https://leetcode.com/problems/count-pairs-whose-sum-is-less-than-target/description/

Это одна из самых простых задач на работу с массивом. Решить можно двумя путями: за O(n^2) и за O(n log n). Наивный перебор первого пути описывать нет смысла, сразу перейду ко второму.

Он включает две стадии:

1. Сортировка массива.
Здесь бутылочное горлышко: общая сложность равна сложности сортировки. Разные методы работают лучше с определенными данными, важно уточнять вид данных. Я взял встроенный метод sort движка V8. В среднем он выполняется за O(n log n).

2. Обработка отсортированного массива.
Выполняется за O(n).
Логика второго шага:
- указатели двигаются навстречу и завершают цикл, когда их значения совпадают.
- на каждой итерации проверяем, выполняется ли условие.
- если условие выполняется, делаем вывод:
☝️условие также будет выполнять пара из элемента sortedArray[left] и любого другого элемента до right, включая и его самого.
тогда вычисляем, сколько всего элементов между left и right, включая right, и добавляем к итоговой сумме пар.
- иначе отбрасываем правый элемент.

Вот код решения:

const countPairs = (nums, target) => {
    const sorted = nums.sort((a, b) => a - b);
    
    let count = 0;
    let left = 0;
    let right = sorted.length - 1;

    while(left < right) {
        if(sorted[left] + sorted[right] < target) {
            count += right - left;
            left++;
        } else {
            right--;
        }
    }

    return count;
};

#leetcode #array #twoPointers