求两个数组的交，并，差，补有什么复杂度较低的算法?

Question

如题，希望有个复杂度较低的算法，indexOf，includes本身也是遍历，算不上复杂度低。new Set是语法糖，也不能算。用ES5实现，不知道有什么复杂度低于o(n*m)的算法？

Answer 1

两个数组的交并差补本来就是个复杂的问题，你还没限定数组的元素是啥，对象你要不要判等？数字和字符串能不能隐式转换？set是写进规范里的，为啥算语法糖？只能用es5，还不能用indexOf，includes，我就不知道用哪些算复杂度低？
最关键
还要复杂度低于o(nm) 复杂度低于o(nm) 复杂度低于o(n*m)
在没给出任何条件却给出这么多限定条件的情况下
题主你想想吧，反正我能力有限，想不出来。
要不你写出来让大家瞅瞅，大家伙给你点赞~(^o^)/~

Answer 2

并 = function(A, B) {

    d = {}

    set = []

    for (k in A) {

        if (!(A[k] in d)){set.push(A[k])}

        d[A[k]] = k

    }

    for (k in B) {

        if (!(B[k] in d)){set.push(B[k])}

        d[B[k]] = k

    }

    return set

}

交 = function(A, B) {

    d = {}

    set = []

    for (k in A) {

        d[A[k]] = k

    }

    for (k in B) {

        if (B[k] in d){set.push(B[k])}

        d[B[k]] = k

    }

    return set

}

差 = function(A, B) {

    d = {}

    set = []

    for (k in B) {

        d[B[k]] = k

    }

    for (k in A) {

        if (!(A[k] in d)){set.push(A[k])}

        d[A[k]] = k

    }

    return set

}

补 = function(A, B) {

    return 差(B, A)

}

> 并([1,2],[1,3,5])

[ 1, 2, 3, 5 ]

> 差([1,2],[1,3,5])

[ 2 ]

> 交([1,2],[1,3,5])

[ 1 ]

> 补([1,2],[1,3,5])

[ 3, 5 ]

>