Здравствуйте, сегодняшняя тема снова возвращается к блогу алгоритмов. Сегодня мы поговорим о вопросе литкода № 724 «Найти опорный индекс. Прежде чем мы попытаемся решить вопрос, мы должны понять, что такое префиксная сумма.
Что такое сумма префикса?
Сумма префиксов в массиве перебирает индекс 1 до последнего и добавляет текущий элемент с предыдущим значением. Люди также называли этот термин кумулятивной суммой, инклюзивным сканированием или сканированием порядкового номера. Интуиция, стоящая за этим, заключается в том, что предыдущая позиция массива префиксов будет иметь сумму предыдущих элементов. Таким образом, мы можем найти общую сумму до определенной точки, проверив значение массива суммы префикса. Нам не нужно каждый раз проходить, чтобы узнать значение между двумя позициями в массиве с массивом суммы префикса. Мы можем эффективно использовать наш код для вычисления значений в массиве суммы префиксов.
Теперь, когда мы знаем, что такое сумма префиксов, давайте решим этот вопрос.
Здесь вопрос:
Чтобы решить этот вопрос, мы можем получить общую сумму всех значений слева направо индекса. Как только мы получим общую сумму, мы можем получить правую и левую сумму в одном цикле, чтобы выполнить условие. С левой суммой мы можем сделать нормальную сумму префиксов слева направо, кумулятивную сумму индекса, чтобы получить левую сумму. Если мы знаем левую сумму, оставшуюся до индекса i, то мы можем получить правую сумму с общей суммой за вычетом левой суммы и текущего индекса, который мы итерируем. Вы можете проверить код ниже для получения дополнительной информации.
Как видите, нам нужно знать только сумму префиксов массива, чтобы получить сумму слева и справа.
Так вот, это сумма префикса. Надеюсь, вам понравится читать!
