在 Go 中使用整数切片进行子集检查

Question

我正在寻找一种有效的方法来检查一个切片是否是另一个切片的子集。我可以简单地遍历它们来检查，但我觉得必须有更好的方法。

例如

{1, 2, 3} 是 {1, 2, 3, 4}
的子集 {1, 2, 2} 不是 {1, 2, 3, 4} 的子集

有效执行此操作的最佳方法是什么？

谢谢！

Answer 1

我认为解决子集问题最常见的方法是通过地图。

package main

import "fmt"

// subset returns true if the first array is completely
// contained in the second array. There must be at least
// the same number of duplicate values in second as there
// are in first.
func subset(first, second []int) bool {
    set := make(map[int]int)
    for _, value := range second {
        set[value] += 1
    }

    for _, value := range first {
        if count, found := set[value]; !found {
            return false
        } else if count < 1 {
            return false
        } else {
            set[value] = count - 1
        }
    }

    return true
}

func main() {
    fmt.Println(subset([]int{1, 2, 3}, []int{1, 2, 3, 4}))
    fmt.Println(subset([]int{1, 2, 2}, []int{1, 2, 3, 4}))
}

检查重复值的能力相对不常见。上面的代码解决了问题（参见：http://play.golang.org/p/4_7Oh-fgDQ）。如果您计划使用重复值，则必须像上面的代码一样进行计数。如果不会有重复值，您可以通过使用布尔值而不是整数来更紧凑地解决问题。

Answer 2

如果您的切片已排序，则可以完成工作。

package main

import "fmt"

// Subset return whether a is a sublist of b. Both a and b must be (weakly) ascending.
func Subset(a, b []int) bool {
    for len(a) > 0 {
        switch {
        case len(b) == 0:
            return false
        case a[0] == b[0]:
            a = a[1:]
            b = b[1:]
        case a[0] < b[0]:
            return false
        case a[0] > b[0]:
            b = b[1:]
        }
    }
    return true
}

func main() {
    cases := []struct {
        a, b []int
        want bool
    }{
        {[]int{1, 2, 3}, []int{1, 2, 3, 4}, true},
        {[]int{1, 2, 2}, []int{1, 2, 3, 4}, false},
    }
    for _, c := range cases {
        if Subset(c.a, c.b) != c.want {
            fmt.Printf("Subset(%v, %v) = %v, want %v\n", c.a, c.b, Subset(c.a, c.b), c.want)
        }
    }
}

Answer 3

检查一个数组是否是golang中另一个数组的子集的算法

package main

import "fmt"

func compare(arr1 []int, arr2 []int) bool {
    for _, num1 := range arr2 {
        status := false
        for _, num2 := range arr1 {
            if num1 == num2 {
                status = true
                break
            }
        }
        if !status {
            return false
        }
    }
    return true
}
func main() {
    arr1 := []int{1, 2, 3, 4, 5}
    arr2 := []int{1, 2, 3}
    if compare(arr1, arr2) {
        fmt.Println("arr2 is subset of arr1")
    } else {
        fmt.Println("arr2 is not subset of arr1")
    }
}