Что такое пересечение массивов?

Пересечение массивов — это операция нахождения всех элементов, которые присутствуют одновременно в двух или более массивах.

// Пример пересечения двух массивов
const array1 = [1, 2, 3, 4, 5];
const array2 = [3, 4, 5, 6, 7];

const intersection = array1.filter(element => array2.includes(element));

console.log(intersection); // Выведет [3, 4, 5]

Основные подходы к реализации:

1. Использование filter и includes: Простой и читаемый подход для небольших массивов. Производительность может снижаться для больших массивов из-за вложенных циклов (filter и includes в худшем случае).

   const intersection = array1.filter(element => array2.includes(element));
   

2. Использование Set: Более эффективный подход для больших массивов, так как проверка наличия элемента в Set имеет временную сложность O(1) в среднем.

   const set2 = new Set(array2);
   const intersection = array1.filter(element => set2.has(element));
   

3. Сортировка и два указателя: Если массивы отсортированы, можно использовать два указателя для линейного прохождения по обоим массивам. Имеет временную сложность O(n log n) за счет сортировки, затем O(n).

   const sortedArray1 = [...array1].sort((a, b) => a - b);
   const sortedArray2 = [...array2].sort((a, b) => a - b);
   
   const intersection = [];
   let i = 0;
   let j = 0;
   
   while (i < sortedArray1.length && j < sortedArray2.length) {
     if (sortedArray1[i] === sortedArray2[j]) {
       intersection.push(sortedArray1[i]);
       i++;
       j++;
     } else if (sortedArray1[i] < sortedArray2[j]) {
       i++;
     } else {
       j++;
     }
   }
   

Выбор метода зависит от размера массивов и требований к производительности. Для небольших массивов filter и includes достаточно, для больших массивов предпочтительнее использовать Set или сортировку.