如何在golang中获得两个切片的交集？

Question

有什么有效的方法来获取Go中两个切片的交集吗？

我想避免嵌套for循环之类的解决方案

slice1 := []string{"foo", "bar","hello"}
slice2 := []string{"foo", "bar"}

intersection(slice1, slice2)
=> ["foo", "bar"]

字符串顺序无关紧要

Answer 1

是的，有几种不同的解决方法。.这是一个可以优化的示例。

package main

import "fmt"

func intersection(a []string, b []string) (inter []string) {
    // interacting on the smallest list first can potentailly be faster...but not by much, worse case is the same
    low, high := a, b
    if len(a) > len(b) {
        low = b
        high = a
    }

    done := false
    for i, l := range low {
        for j, h := range high {
            // get future index values
            f1 := i + 1
            f2 := j + 1
            if l == h {
                inter = append(inter, h)
                if f1 < len(low) && f2 < len(high) {
                    // if the future values aren't the same then that's the end of the intersection
                    if low[f1] != high[f2] {
                        done = true
                    }
                }
                // we don't want to interate on the entire list everytime, so remove the parts we already looped on will make it faster each pass
                high = high[:j+copy(high[j:], high[j+1:])]
                break
            }
        }
        // nothing in the future so we are done
        if done {
            break
        }
    }
    return
}

func main() {
    slice1 := []string{"foo", "bar", "hello", "bar"}
    slice2 := []string{"foo", "bar"}
    fmt.Printf("%+v\n", intersection(slice1, slice2))
}

现在上面定义的交集方法将只运行在slices的strings，比如你的例子。您可以在理论上创建一个定义，这个样子的func intersection(a []interface, b []interface) (inter []interface)，但是你会依靠反射和类型转换，这样就可以比较，这将增加延迟和使您的代码更难阅读。对于您关心的每种类型，维护和阅读以编写单独的函数可能更容易。

func intersectionString(a []string, b []string) (inter []string)，

func intersectionInt(a []int, b []int) (inter []int)，

func intersectionFloat64(a []Float64, b []Float64) (inter []Float64)，..ect

然后，您可以创建自己的包并在确定要实现的方式后重用。

package intersection

func String(a []string, b []string) (inter []string)

func Int(a []int, b []int) (inter []int)

func Float64(a []Float64, b []Float64) (inter []Float64)