Задача: 1099. Two Sum Less Than K
Сложность: easy

Дан массив целых чисел nums и целое число k. Верните максимальную сумму, такую что существуют i < j, при которых nums[i] + nums[j] = sum и sum < k. Если не существует таких i и j, удовлетворяющих этому условию, верните -1.

Пример:

Input: nums = [34,23,1,24,75,33,54,8], k = 60
Output: 58
Explanation: We can use 34 and 24 to sum 58 which is less than 60.

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

1⃣Отсортируйте массив.

2⃣Установите указатели: левый на начало массива, правый на конец.

3⃣Пока левый указатель меньше правого:
Если сумма элементов по указателям меньше k, обновите максимальную сумму и сдвиньте левый указатель вправо.
Иначе сдвиньте правый указатель влево.
Верните максимальную сумму.

😎 Решение:

class Solution {
    function twoSumLessThanK($nums, $k) {
        $answer = -1;
        $count = array_fill(0, 1001, 0);
        foreach ($nums as $num) {
            $count[$num]++;
        }
        $lo = 1;
        $hi = 1000;
        while ($lo <= $hi) {
            if ($lo + $hi >= $k || $count[$hi] == 0) {
                $hi--;
            } else {
                if ($count[$lo] > ($lo < $hi ? 0 : 1)) {
                    $answer = max($answer, $lo + $hi);
                }
                $lo++;
            }
        }
        return $answer;
    }
}

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