Задача: 923. 3Sum With Multiplicity
Сложность: medium

Если задан целочисленный массив arr и целое число target, верните количество кортежей i, j, k, таких, что i < j < k и arr[i] + arr[j] + arr[k] == target. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

👨‍💻 Алгоритм:

1⃣Отсортировать массив arr.

2⃣Инициализировать счетчик для количества кортежей.
Пройти по массиву тремя указателями i, j, и k:
Для каждого i, установить j на i + 1, и k на конец массива.
Использовать двухуказательный метод для нахождения пар (j, k), таких что arr[i] + arr[j] + arr[k] == target.

3⃣Вернуть результат по модулю 10^9 + 7.

😎 Решение:

var threeSumMulti = function(arr, target) {
    arr.sort((a, b) => a - b);
    const MOD = 10**9 + 7;
    let count = 0;
    
    for (let i = 0; i < arr.length; i++) {
        let j = i + 1, k = arr.length - 1;
        
        while (j < k) {
            let sum = arr[i] + arr[j] + arr[k];
            if (sum === target) {
                if (arr[j] === arr[k]) {
                    count += (k - j + 1) * (k - j) / 2;
                    break;
                } else {
                    let left = 1, right = 1;
                    while (j + 1 < k && arr[j] === arr[j + 1]) {
                        left++;
                        j++;
                    }
                    while (k - 1 > j && arr[k] === arr[k - 1]) {
                        right++;
                        k--;
                    }
                    count += left * right;
                    j++;
                    k--;
                }
            } else if (sum < target) {
                j++;
            } else {
                k--;
            }
        }
    }
    
    return count % MOD;
};

Ставь 👍 и забирай 📚 Базу знаний