Задача: 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.

😎 Решение:

function threeSumMulti($arr, $target) {
    sort($arr);
    $MOD = 1_000_000_007;
    $count = 0;
    
    for ($i = 0; $i < count($arr); $i++) {
        $j = $i + 1;
        $k = count($arr) - 1;
        while ($j < $k) {
            $sum = $arr[$i] + $arr[$j] + $arr[$k];
            if ($sum == $target) {
                if ($arr[$j] == $arr[$k]) {
                    $count += ($k - $j + 1) * ($k - $j) / 2;
                    break;
                } else {
                    $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--;
                }
            } elseif ($sum < $target) {
                $j++;
            } else {
                $k--;
            }
        }
    }
    
    return $count % $MOD;
}

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