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

Question

I have two slices:

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

Expected result:

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

What's the best way to create a slice from duplicate items of slice1 and slice2 with this specifications:

1. Minimum code
2. Slices are large
3. Slices are not sorted
4. Do not modify the slices
5. They may not contain the duplicates

This is what I have tried:

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

This method sacrifices memory usage for big O complexity (speed).

// 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

You only visit each of the elements once, but the memory requirements are much larger as slice1 needs to be stored in the map.

You could extend this code to flatten the smallest of the 2 slices into the map, for less memory requirements.

it's worth noting that map[string]struct{} is used instead of map[string]bool because struct{} uses zero bytes of memory