Совершенные подотрезки
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Словари и множества
- Массивы и списки
- Математика
Дан массив целых чисел (по модулю не больше 100). Подотрезок — непустая непрерывная часть массива; он совершенный, если сумма его элементов — точный квадрат неотрицательного целого (0, 1, 4, 9, 16, …). Подотрезки с разными границами считаются разными, даже если значения в них совпадают.
Верните количество совершенных подотрезков. Длина массива может достигать 10^5, поэтому перебирать все подотрезки нельзя.
Пример: [4, 0, 0, 16] → 9.
Источник: Coding Competitions Archive, kickstart/2020/round_c/perfect_subarray · © Google LLC · Apache-2.0 · условие переведено и дополнено
Решить онлайнБесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).