Почему это работает
- Каждое число заранее знает свою пару: сумма минус само число. Вопрос только в том, встречали ли мы её раньше, и словарь отвечает на него сразу.
- Сначала ищем, потом записываем. Иначе первая 5 нашла бы в словаре саму себя и вернула [0, 0].
- Если пара стоит на j < i, то когда мы дойдём до i, число с индекса j уже будет в словаре. Значит, пару не пропустим, и хватает одного прохода.
Сложность
Время O(n): один проход, а поиск и запись в словаре в среднем O(1). Память O(n): в словаре могут оказаться все числа.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗