машинопись: определить, есть ли в 2 списках хотя бы один общий элемент

Question

У меня есть 2 списка целых чисел, которые являются L1 и L2.

L1 и L2 могут быть любой длины (0,1 или много)

Я строю метод, который должен возвращать false, если какой-либо элемент L1 отсутствует в L2, и true в противном случае:

Я делаю это:

private myMethod(L1: int[],L2: int[])
{
    return L1.every(L1element => L2.includes(L1element))
}

С этим кодом все работает хорошо, но мне интересно, если я делаю наиболее эффективным способом: причина для каждого элемента L1 (по крайней мере, первого и до последнего в худшем случае) Я выполняю итерации для каждого элемента L2 (по крайней мере, первого и до последнего в худшем случае) , поэтому стоимость, если о (длина L1 * длина L2), если я не ошибаюсь. Было бы невозможно улучшить производительность, сначала отсортировав 2 списка, или есть какой-то способ, я немного проверил и некоторые разговоры о пересечении, но я не знаю, что делает это пересечение под капотом, он делает то же самое, что и я?

Answer 1

Вы можете сначала создать Набор из L2, а затем вместо .includes (что составляет O(n)), используйте .has (что составляет O(1)):

private myMethod(L1: int[],L2: int[])
{
    const L2Set = new Set(L2);
    return L1.every(L1element => L2Set.has(L1element));
}

Это уменьшает общую сложность с O(n ^ 2) до O(n).