Сложность: easy
Разработайте структуру данных, которая принимает поток целых чисел и проверяет, есть ли в ней пара чисел, сумма которых равна определенному значению.
Реализуйте класс TwoSum:
- TwoSum() инициализирует объект TwoSum с изначально пустым массивом.
- void add(int number) добавляет число в структуру данных.
- boolean find(int value) возвращает true, если существует хотя бы одна пара чисел, сумма которых равна значению value, в противном случае возвращает false.
Пример:
Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]
👨💻 Алгоритм:
1️⃣Инициализация указателей: Инициализируйте два указателя low и high, которые указывают на первый и последний элементы списка соответственно.
2️⃣Итерация с использованием двух указателей: Запустите цикл для итерации по списку. Цикл завершится, когда будет найдено решение с двумя суммами или когда два указателя встретятся. На каждом шаге цикла перемещайте один из указателей в зависимости от различных условий: Если сумма элементов, на которые указывают текущие указатели, меньше желаемого значения, то необходимо попытаться увеличить сумму для достижения желаемого значения, то есть переместить указатель low вперёд для получения большего значения. Если сумма элементов больше желаемого значения, то следует попытаться уменьшить сумму, перемещая указатель high в сторону указателя low. Если сумма равна желаемому значению, можно сразу выполнить возврат из функции.
3️⃣Завершение цикла: Если цикл завершается тем, что два указателя встречаются, то можно быть уверенным, что решения для желаемого значения не существует.
😎 Решение:
class TwoSum(object):
def __init__(self) -> None:
self.nums = []
self.is_sorted = False
def add(self, number: int) -> None:
self.nums.append(number)
self.is_sorted = False
def find(self, value: int) -> bool:
if not self.is_sorted:
self.nums.sort()
self.is_sorted = True
low, high = 0, len(self.nums) - 1
while low < high:
currSum = self.nums[low] + self.nums[high]
if currSum < value:
low += 1
elif currSum > value:
high -= 1
else: return True
return False
Ставь 👍 и забирай 📚 Базу знаний