从两个切片的重复项创建切片

Question

我有两片:

slice1 := []string{"a", "b", "c", "d"}
slice2 := []string{"c", "d", "e", "f"}

预期结果:

[]string{"c", "d"}

什么是创建的重复项片的最佳方式slice1,并slice2与该规格:

1. 最低代码
2. 切片很大
3. 切片没有排序
4. 不要修改切片
5. 它们可能不包含重复项

这是我尝试过的:

slice1 := []string{"a", "b", "c", "d"}
slice2 := []string{"c", "d", "e", "f"}
duplicateItems := []string{}
for _, item1 := range slice1 {
    for _, item2 := range slice2 {
        if item1 == item2 {
            duplicateItems = append(duplicateItems, item1)
        }
    }
}

fmt.Println(duplicateItems) // [c d]

Answer 1

这种方法牺牲了大O复杂度(速度)的内存使用.

// flatten the first slice into a map for O(1) constant time lookup
m1 := make(map[string]struct{})
for _, v := range slice1 {
    m1[v] = struct{}{}
}

var dup []string

// iterate slice 2, using the O(1) lookup.
for _, v := range slice2 {
    if _, exists := m1[v]; exists {
        dup = append(dup, v)
    }
}

// dup contains the duplicates

您只访问每个元素一次,但内存要求要大得多,因为slice1需要存储在地图中.

您可以扩展此代码以将2个切片中的最小切片压平到地图中,以减少内存需求.

值得注意的map[string]struct{}是,使用而不是map[string]bool因为struct{}使用零字节的内存