▲

3

▼

💡 Элегантный подсчёт допустимых разбиений массива путём трекинга баланса

leetcoder, 03-01-2025 , 229

Следуюшая задача для нашего разбора: 2270. Number of Ways to Split Array.

Описание задачи 📝

Дан массив целых чисел nums длины n. Требуется найти количество индексов i, где выполняются следующие условия:

• Сумма первых i+1 элементов массива больше или равна сумме оставшихся элементов.
• Индекс i удовлетворяет 0≤i<n−1, то есть правая часть должна содержать хотя бы один элемент.

Идея 💡

Вместо того чтобы каждый раз вычислять суммы левой и правой частей массива, мы используем баланс для их трекинга.
Изначально баланс равен −total_sum, где total_sum — сумма всех элементов массива. На каждом шаге баланс обновляется с помощью текущего элемента, а проверка условий выполняется через простое сравнение баланса с нулём.

Подробности подхода 🛠️

1. Вычислить сумму всех элементов массива и сохранить её в total_sum.
2. Проитерироваться по массиву до предпоследнего элемента:
   • Обновить баланс, добавляя 2×текущий элемент.
   • Если баланс становится больше или равен нулю, увеличивать счётчик допустимых разбиений.
3. Вернуть итоговый счётчик, который отражает количество валидных разбиений.

Асимптотика ⏱️

• Временная сложность: O(n), где n — длина массива. Один проход используется для вычисления суммы, другой — для проверки условий.
• Пространственная сложность: O(1), так как используется лишь фиксированное количество переменных.

Исходный код 💻

impl Solution {
    pub fn ways_to_split_array(nums: Vec<i32>) -> i32 {
        // Calculate the total sum of the array as i64 to avoid overflow
        let total_sum: i64 = nums.iter().map(|&n| n as i64).sum();

        // Use fold to calculate the number of valid splits
        nums[..nums.len() - 1]
            .iter()
            .fold((0, -total_sum), |(valid_splits, current_balance), &current_num| {
                // Update the balance
                let updated_balance = current_balance + 2 * current_num as i64;

                // Check if the split is valid
                let updated_splits = valid_splits + if updated_balance >= 0 { 1 } else { 0 };

                // Return the updated state
                (updated_splits, updated_balance)
            })
            .0 // Extract the count of valid splits from the result tuple
    }
}