2215. Find the Difference of Two Arrays

Задача

Даны два массива целых чисел nums1 и nums2 с индексацией от 0. Необходимо вернуть список answer размером 2, где:

• answer - список всех уникальных целых чисел из nums1, которые отсутствуют в nums2
• answer - список всех уникальных целых чисел из nums2, которые отсутствуют в nums1

Порядок элементов в списках не важен.

Примеры

Пример 1

Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]

Пояснение

В nums1 нет в nums2 чисел 1 и 3 → answer[0] = [1,3]. В nums2 нет в nums1 чисел 4 и 6 → answer[1] = [4,6].

Пример 2

Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]

Пояснение

В nums1 нет в nums2 только числа 3 (учитывается один раз) → answer[0] = [3]. Все числа nums2 есть в nums1 → answer[1] = [].

Решение

Решение

// Временная сложность: O(N + M)
// Пространственная сложность: O(N + M)
 
var findDifference = function(nums1, nums2) {
    // O(N) - создание Set (проход по всем элементам nums1)
    // O(N) space - память под хранение уникальных элементов
    const s1 = new Set(nums1);
 
    // O(M) - создание Set (проход по всем элементам nums2)
    // O(M) space
    const s2 = new Set(nums2);
 
    // [...s1] - это O(N)
    // .filter - проходит по N элементам
    // .has(x) - выполняется за O(1)
    // Итого строка: O(N)
    const res1 = [...s1].filter(x => !s2.has(x));
 
    // Аналогично: O(M)
    const res2 = [...s2].filter(x => !s1.has(x));
 
    return [res1, res2];
};

Решение 2 (Two Pointers + HashMap)

// Временная сложность: O(N + M)
// Пространственная сложность: O(N + M)
 
var findDifference = function(nums1, nums2) {
    const map1 = new Map();
    const map2 = new Map();
 
    // O(N) — ключи остаются числами
    for (const num of nums1) map1.set(num, true);
    // O(M)
    for (const num of nums2) map2.set(num, true);
 
    const res1 = [];
    const res2 = [];
 
    for (const key of map1.keys()) {
        if (!map2.has(key)) {
            res1.push(key);
        }
    }
 
    for (const key of map2.keys()) {
        if (!map1.has(key)) {
            res2.push(key);
        }
    }
 
    return [res1, res2];
};