2270. Количество способов разделить массив

]

сложно: medium

]

темы: array, prefix sum

вам дают 0-indexed целочисленные массивы длины n.

Nums содержит vallog Split в индексе I, если следующее является true:

]
• сумма первых элементов I 1 - больше, чем или равна сумма последнего n - i - 1 элементов.
]
• есть , по крайней мере, один элемент справа от i. То есть 0 ]

]

return число vally splits in nums .

]

пример 1:

]

]
• ] input: nums = [10,4, -8,7]
]
• ] output: 2
]
• ] Объяснение: есть три способа разделения Nums на две непустые части:
  ]
  • разделение Nums в индексе 0. Затем первая часть равен [10], а ее сумма составляет 10. Вторая часть-[4, -8,7], а ее сумма-3. Поскольку 10> = 3, i = 0-допустимое разделение.
  ]
  • разделенные Nums в индексе 1. Затем первая часть -[10,4], а его сумма -14. Вторая часть -[-8,7], а ее сумма --1. Поскольку 14> = -1, i = 1 является действительным разделением.
  ]
  • разделение Nums в индексе 2. Затем первая часть-[10,4, -8], а его сумма-6. Вторая часть-[7], а ее сумма 7. Поскольку 6 ]
  • Таким образом, количество допустимых расщеплений в NUMS составляет 2.
  ]
  ]
]

]

пример 2:

]
• ] input: nums = [2,3,1,0]
]
• ] output: 2
]
• ] Объяснение: есть два действительных расщепления в Nums:
  ]
  • разделенные Nums в индексе 1. Затем первая часть - [2,3], а его сумма - 5. Вторая часть - [1,0], а ее сумма - 1. Поскольку 5> = 1, i = 1 - допустимое разделение.
  ]
  • разделение Nums в индексе 2. Затем первая часть - [2,3,1], а их сумма - 6. Вторая часть - [0], а ее сумма 0. Поскольку 6> = 0, i = 2 - допустимое разделение.
  ]
  ]
]

ограничения:

]

2 5 ] -10
• 5 ^{5 ]}
]

Намекать:

]

для любого индекса I, как мы можем найти сумму первых (I 1) элементов из суммы первых элементов I?
1. ]
, если общая сумма массива известна, как мы можем проверить, является ли сумма первых (i 1) элементов, превышающих или равную оставшимся элементам?
2. ]
]

Решение:

мы можем подойти к нему, используя следующие шаги:

] Подход:

]

]

]
1. prefix sum : во -первых, мы вычисляем кумулятивную сумму массива слева, которая помогает в проверке суммы первых элементов I 1. ]
]
2. общая сумма : вычислять общую сумму массива, которая полезна при проверке, если сумма оставшихся элементов меньше или равна сумме первых элементов I 1.
]
3. итерация над массивом : для каждого действительного индекса I (где 0 ]
]
4. эффективность : вместо повторного перечисления сумм используйте сумму префикса и общую сумму для эффективных сравнений. ]
]

давайте реализуем это решение в PHP:

2270. Количество способов разделения массива ]
]

Php /** * @param integer [] $ nums * @return Integer */ функция waystosplitarray ($ nums) { ... ... ... /** * Перейти к ./solution.php */ } // Пример использования: $ nums1 = [10, 4, -8, 7]; echo waystosplitarray ($ nums1); // Вывод: 2 $ nums2 = [2, 3, 1, 0]; echo waystosplitarray ($ nums2); // Вывод: 2 ?>

] Объяснение:

]

]

]
1. $ totalsum : эта переменная хранит сумму всех элементов в массиве Nums. ]
]
2. $ prefixsum : эта переменная отслеживает совокупную сумму элементов слева (до индекса i). ]
]
3. $ steriansum : это сумма оставшихся элементов от индекса I 1 до конца массива. Он рассчитывается путем вычитания $ prefixsum из $ totalsum. ]
]
4. Valid Split Check : Для каждого индекса I проверяем, больше ли сумма префикса или равна оставшейся сумме. ]
]

] Сложность времени:

]

]

]
• o (n) : мы разбираемся через массив один раз, чтобы вычислить сумму, и еще раз, чтобы проверить действительные разделения. Следовательно, временная сложность является линейной по отношению к длине массива. ]
]

] Сложность пространства:

]

]

]
• o (1) : мы используем только несколько дополнительных переменных ($ totalsum, $ prefixsum, $ storingsum), поэтому сложность пространства постоянна.
]

контактные ссылки ]

Если вы нашли эту серию полезной, пожалуйста, рассмотрите возможность предоставить

Repository звезду на GitHub или поделиться постом в ваших любимых социальных сетях? Ваша поддержка будет много значить для меня! ]

, если вы хотите более полезный контент, подобный этому, не стесняйтесь следить за мной:

]

]

• LinkedIn ]
• github
]

] ]