Почему это работает
- Найти одну тройку мало: ответ — края блока троек. Поэтому при совпадении прогон записывает индекс и идёт дальше: влево в первом поиске, вправо во втором.
- В первом поиске всё левее lo меньше искомого, а всё правее hi — искомое или больше. Когда lo обгоняет hi, последнее записанное совпадение — самое левое. Второй поиск — зеркальный.
- Если остановиться на совпадении и шагать от него в стороны по одному, на массиве из одних троек выйдет O(n). Два поиска дают O(log n) при любом блоке.
Сложность
Время O(log n): два бинарных поиска друг за другом. Память O(1).
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗