▲

3

▼

💡 Проверка существования элемента совместно со своим удвоением

leetcoder, 01-12-2024 , 357

Наступление зимы отметим разбором простой задачи 1346. Check If N and Its Double Exist.

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

Дан массив целых чисел arr. Нужно определить, существуют ли такие индексы i и j, что:
- i≠j,
- arr[i]=2⋅arr[j].

Обзор решения 🚀

Решение использует два простых прохода по массиву:

1. Первый проход:
   • Создаем хеш-таблицу, где для каждого элемента записываем количество его удвоенных значений.
2. Второй проход:
   • Проверяем, существует ли текущий элемент в хеш-таблице.
   • Для нуля (0) дополнительно проверяем, встречается ли он в массиве как минимум дважды (так как 2⋅0=0).

Временная сложность ⏱️

• Первый проход: O(n) — построение хеш-таблицы.
• Второй проход: O(n) — проверка условий.
• Итоговая сложность: O(n).

Пространственная сложность 📦

• O(n) — память для хеш-таблицы.

Исходый код решения

use std::collections::HashMap;

impl Solution {
    pub fn check_if_exist(arr: Vec<i32>) -> bool {
        let mut double_map = HashMap::new();

        // Populate the map with counts of doubled values
        for &num in &arr {
            *double_map.entry(2 * num).or_insert(0) += 1;
        }

        // Check for the required condition
        for &num in &arr {
            if num == 0 {
                // Special case for 0 (2 * 0 == 0)
                if *double_map.get(&0).unwrap_or(&0) > 1 {
                    return true;
                }
            } else if double_map.get(&num).is_some() {
                return true;
            }
        }

        false
    }
}