Самый длинный равновесный подмассив данного массива

Опубликовано: 19 Сентября, 2022

Для целочисленного массива arr размера N[] задача состоит в том, чтобы найти самый длинный равновесный подмассив, т. е. такой подмассив, что сумма префиксов оставшегося массива совпадает с суммой суффиксов.

Примеры:

Input: N = 3, arr[] =  {10, 20, 10}
Output: 1
Explanation: The longest subarray is {20}. The remaining prefix is {10} and suffix is {10}.
Therefore only one element in the subarray.

Input: N = 6, arr[] = {2, 1, 4, 2, 4, 1}
Output: 0
Explanation: The longest subarray is of size 0. 
The prefix is {2, 1, 4} and suffix is {2, 4, 1} and both has some 7.

 Input: N = 5, arr[] = {1, 2, 4, 8, 16}
Output: -1

Подход: Эту проблему можно решить с помощью двух указателей, основанных на следующей идее:

Traverse from both the end. If the sum of prefix is less then increment the front pointer, otherwise, do the opposite. In this way we will get the minimum number of elements in prefix and suffix. So the subarray will have the maximum length because the remaining array has minimum elements.

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

  • Пусть i будет левым указателем изначально в 0, а j будет правым указателем изначально в N-1 .
  • Во-первых, мы проверим, равна ли сумма всех элементов 0 или нет. Если 0, то весь массив будет подмассивом.
  • Инициализируйте две переменные prefixSum = 0 и suffixSum = 0 .
  • Обход массива от до i не равен j .
    • Если prefixSum <= suffixSum , то добавьте arr[i] в prefixSum . И увеличить i на единицу.
    • В противном случае проверьте, что если prefixSum > suffixSum , то добавьте add arr[i] в suffixSum . И уменьшить j на единицу.
    • Теперь проверьте, что если prefixSum равен suffixSum , то возвращает разницу между i и j .
  • В противном случае вернуть -1.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ