Задача: 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:
    def twoSumLessThanK(self, nums, k):
        answer = -1
        count = [0] * 1001
        for num in nums:
            count[num] += 1
        lo, hi = 1, 1000
        while lo <= hi:
            if lo + hi >= k or count[hi] == 0:
                hi -= 1
            else:
                if count[lo] > (0 if lo < hi else 1):
                    answer = max(answer, lo + hi)
                lo += 1
        return answer

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