Количество подмассивов, содержащих длину этого подмассива

Учитывая массив A[] длины N , задача состоит в том, чтобы подсчитать количество подмассивов A[] , содержащих длину этого подмассива.

Примеры:

Input: A = {10, 11, 1}, N = 3
Output: 1
Explanation: Only the subarray {1}, with a length 1, contains its own length.

Input: A = [1, 2, 3, 4, 5], N = 5
Output: 9
Explanation: The subarrays {1}, {1, 2}, {2, 3}, {1, 2, 3}, {2, 3, 4}, {3, 4, 5},  
{1, 2, 3, 4}, {2, 3, 4, 5}, {1, 2, 3, 4, 5} contain their own length.

Подход: следуйте приведенной ниже идее, чтобы решить проблему:

First, form each and every subarray of A. Then, check if the length of the subarray is present in that subarray.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Перебрать массив от i = 0 до N :
  • Итерация во вложенном цикле от j = i до N :
  • Создается подмассив от i до j .
  • Пройдите по подмассиву и проверьте, присутствует ли длина в подмассиве.
  • Если есть, то увеличиваем счетчик .
• Окончательный счет является требуемым ответом.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ³ )
Вспомогательное пространство: O(1)