Почему это работает
- У каждой цепочки одно начало: число, для которого x − 1 в множестве нет. Число, у которого x − 1 есть, сидит внутри чужой цепочки, и его сразу пропускаем.
- От начала цепочку считаем вверх, x + 1, x + 2, пока следующее число есть в множестве. На каждый такой вопрос множество отвечает за один шаг.
- Поэтому каждое число проходим внутри цепочки не больше одного раза, и цикл в цикле всё равно делает O(n) шагов в сумме.
Сложность
Время O(n): поиск в множестве в среднем O(1), а каждое число попадает в подсчёт не больше одной цепочки. С сортировкой было бы O(n log n). Память O(n) на множество.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗