在Go语言的实际开发中，判断一个整数切片是否为另一个整数切片的子集是较为常见的需求，比如校验用户权限集合是否包含所需的权限项、过滤数据时判断目标数据是否在允许的范围内等场景都会用到这类逻辑。不同的实现方式在性能和适用场景上有明显区别，下面介绍两种常用的高效实现方法。
方法一：基于map统计元素出现次数
这种方法的思路是先统计父切片中每个整数的出现次数，再遍历子切片，逐个检查每个元素在父切片中的出现次数是否足够，如果所有元素都满足要求，则子切片是父切片的子集。
实现步骤
- 创建一个map，键为整数，值为该整数在父切片中的出现次数
- 遍历父切片，统计每个元素的出现次数存入map
- 遍历子切片，对每个元素检查map中对应的次数是否大于0，如果大于0则次数减1，否则返回false
- 遍历完子切片所有元素后返回true
代码示例
package main
import "fmt"
// 判断sub是否为parent的子集，允许重复元素
func isSubsetByMap(parent, sub []int) bool {
// 统计parent中每个元素的出现次数
countMap := make(map[int]int)
for _, num := range parent {
countMap[num]++
}
// 检查sub中的每个元素
for _, num := range sub {
if countMap[num] <= 0 {
return false
}
countMap[num]--
}
return true
}
func main() {
parent := []int{1, 2, 3, 4, 2, 5}
sub1 := []int{2, 3, 2}
sub2 := []int{2, 3, 6}
fmt.Println(isSubsetByMap(parent, sub1)) // 输出 true
fmt.Println(isSubsetByMap(parent, sub2)) // 输出 false
}
复杂度分析
该方法的时间复杂度为O(n+m)，其中n是父切片的长度，m是子切片的长度，只需要两次遍历即可完成判断。空间复杂度为O(k)，k是父切片中不同整数的个数，需要额外的map存储元素计数。
这种方法的优势是支持切片中存在重复元素，并且不需要修改原切片的内容，适合大多数通用场景。
方法二：基于排序加双指针
如果允许对原切片进行排序，或者可以接受复制切片后排序，那么可以使用排序加双指针的方法，这种方法不需要额外的map空间，适合对空间要求较高的场景。
实现步骤
- 分别对父切片和子切片进行排序（如果原切片不能修改，需要先复制再排序）
- 使用两个指针分别指向两个切片的开头，逐个比较元素
- 如果父切片指针指向的元素小于子切片指针指向的元素，父切片指针后移
- 如果两者相等，两个指针都后移
- 如果父切片指针指向的元素大于子切片指针指向的元素，说明子切片的元素不在父切片中，返回false
- 如果子切片指针遍历完所有元素，说明是子集，返回true
代码示例
package main
import (
"fmt"
"sort"
)
// 判断sub是否为parent的子集，假设切片中无重复元素，或者不需要考虑重复次数
func isSubsetBySort(parent, sub []int) bool {
// 复制切片避免修改原数据
pCopy := make([]int, len(parent))
copy(pCopy, parent)
sCopy := make([]int, len(sub))
copy(sCopy, sub)
// 排序
sort.Ints(pCopy)
sort.Ints(sCopy)
// 双指针遍历
i, j := 0, 0
for i < len(pCopy) && j < len(sCopy) {
if pCopy[i] < sCopy[j] {
i++
} else if pCopy[i] == sCopy[j] {
i++
j++
} else {
return false
}
}
// 如果子切片的所有元素都匹配完成，说明是子集
return j == len(sCopy)
}
func main() {
parent := []int{5, 1, 3, 2, 4}
sub1 := []int{2, 3, 1}
sub2 := []int{2, 3, 6}
fmt.Println(isSubsetBySort(parent, sub1)) // 输出 true
fmt.Println(isSubsetBySort(parent, sub2)) // 输出 false
}
复杂度分析
该方法的时间复杂度为O(n log n + m log m)，主要是排序的时间开销，双指针遍历的时间复杂度为O(n+m)。空间复杂度为O(n+m)，如果允许修改原切片，可以省去复制的空间，空间复杂度可以降为O(1)。
这种方法的劣势是会改变切片的元素顺序，或者需要额外的复制空间，并且无法正确处理重复元素的次数校验，比如父切片只有一个2，子切片有两个2的情况会误判为true。
两种方法的适用场景对比
| 对比维度 | map统计法 | 排序双指针法 |
|---|---|---|
| 是否支持重复元素校验 | 支持 | 不支持 |
| 时间复杂度 | O(n+m) | O(n log n + m log m) |
| 空间复杂度 | O(k)，k为不同元素个数 | O(1)（允许修改原切片时） |
| 是否修改原切片 | 不修改 | 修改或需要复制 |
| 适用场景 | 通用场景，尤其是有重复元素的情况 | 无重复元素、对空间要求高、允许排序的场景 |
总结
在Go语言中判断整数切片子集时，优先推荐使用map统计的方法，该方法通用性强，性能稳定，支持重复元素校验，且不会修改原切片内容。如果明确切片中没有重复元素，且对空间占用有严格要求，同时可以接受排序操作，那么可以选择排序双指针的方法。开发者可以根据实际的业务场景和性能要求选择最合适的实现方式。