▲

3

▼

🚀 Решение в функциональном стиле для наилучшей суммы пар с одинаковой суммой цифр

leetcoder, 12-02-2025 , 163

Ссылка на задачу – 2342. Max Sum of a Pair With Equal Sum of Digits

📌 Условие задачи

Дан массив положительных чисел nums. Необходимо найти максимальную сумму двух различных элементов, у которых одинаковая сумма цифр. Если таких пар нет — вернуть -1.

💡 Идея решения

Вместо хранения всех чисел с одинаковой суммой цифр, достаточно хранить только максимальное из них.
Таким образом, при встрече нового числа с такой же суммой цифр можно сразу проверять, образует ли оно лучшую пару.

🔍 Подход к решению

1. Используем массив max_per_dsum, в котором храним наибольшее число для каждой суммы цифр.
   • Максимальная сумма цифр для i32 — 82, но мы ограничиваем массив сотней для простоты.
2. Обрабатываем nums за один проход, применяя функциональный стиль с filter_map:
   • вычисляем сумму цифр d_sum для числа n;
   • если уже есть число с таким d_sum, определяем текущую сумму пары и сохраняем обновлённое максимальное число;
   • если это первое число с данным d_sum, просто сохраняем его в max_per_dsum;
   • filter_map отбрасывает неопределённые суммы пар (None), оставляя только валидные.
3. Выбираем наибольшую возможную сумму пары, используя max().

📊 Оценка сложности

• Временная сложность: O(n), так как мы проходим по nums один раз и выполняем O(1) операций.
• Дополнительная память: O(1), так как массив d_sum_best имеет фиксированный размер 100.

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

impl Solution {
    pub fn maximum_sum(nums: Vec<i32>) -> i32 {
        const DIGIT_SUM_LIMIT: usize = 100; // Max digit sum for i32 is 82, 100 is a safe upper bound
        let mut max_per_dsum = [None as Option<i32>; DIGIT_SUM_LIMIT]; // Stores the largest number for each digit sum

        nums.into_iter().filter_map(|n| {
            let d_sum = Self::digit_sum(n) as usize;

            let (cur_sum, new_max) = match max_per_dsum[d_sum] {
                Some(prev_max) => (Some(prev_max + n), prev_max.max(n)), // Compute sum and update max number
                None => (None, n) // First occurrence of this digit sum
            };

            max_per_dsum[d_sum] = Some(new_max);
            cur_sum // Only return valid sums
        }).max().unwrap_or(-1) // Convert `None` to `-1` if no valid pair is found
    }

    // Helper function to compute the sum of digits of a number
    fn digit_sum(mut n: i32) -> i32 {
        let mut sum = 0;
        while n > 0 {
            sum += n % 10;
            n /= 10;
        }
        sum
    }
}

Tags: #rust #algorithms