Задача на сегодня 3152. Special Array II.
📝 Условие:
- Нам дан массив
nums и запросы queries.
- Для каждого запроса
[from, to] нужно проверить, является ли подмассив nums[from..=to] "особым".
- Подмассив считается "особым", если каждая пара соседних элементов в нём имеет разную чётность (один чётный, другой нечётный).
🧠 Идея:
- Решение основано на идее "вычисли один раз — используй много раз".
- Сначала выполняем линейные предвычисления префиксных количеств пар соседних элементов разной чётности.
- Затём каждый запрос обрабатывается мгновенно за
O(1), что делает решение особенно эффективным для больших массивов и множества запросов 😊
💡 Подход:
-
Префиксная сумма:
- Создаём массив
prefix_count, где prefix_count[i] хранит количество пар соседних элементов с разной чётностью от начала массива до индекса i.
- Заполняем его за
O(n) в одном проходе.
-
Обработка запросов:
- Для каждого запроса
[from, to] считаем количество таких пар в диапазоне через разность: prefix_count[to] - prefix_count[from].
- Если это число равно
to − from, подмассив является "особым".
-
Возвращаем массив булевых значений для каждого запроса.
⏱️ Сложность:
- Время:
- Предварительная обработка:
O(n).
- Обработка всех запросов:
O(q), где q — количество запросов.
- Итоговая сложность:
O(n+q).
- Память:
O(n) для хранения массива prefix_count.
Исходный код решения
impl Solution {
pub fn is_array_special(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<bool> {
let n = nums.len();
// prefix_count[i]: number of index-pairs (j, j+1) <= i with different parity
let mut prefix_count = vec![0; n];
for i in 0..n - 1 {
prefix_count[i + 1] = prefix_count[i] + (nums[i] + nums[i + 1]) % 2;
}
// Processing queries
let mut answers = Vec::with_capacity(queries.len());
for query in queries {
let from = query[0];
let to = query[1];
let diff = prefix_count[to as usize] - prefix_count[from as usize];
answers.push(diff == to - from);
}
answers
}
}