Go语言中如何高效检测[][]int中的重复[]int切片？

针对你需要检测有序[][]int中重复子集（遇到第一个重复即返回错误）的需求，下面提供两种符合Go惯用风格的高效实现方案，并分析各自的适用场景：

方案一：哈希表+唯一标识（推荐优先使用） #

Go不允许直接将[]int作为map的键，但可以将有序子集转换为可哈希的唯一标识（字符串或哈希值），通过map记录已出现的子集，遍历过程中发现重复立即返回。

实现1：字符串编码（无碰撞风险） #

利用字符串拼接将有序子集转为唯一字符串，避免哈希碰撞问题，实现简单直观：

import (
	"fmt"
	"strconv"
	"strings"
)

func check(setOfSubsets [][]int) error {
	seen := make(map[string]struct{})
	for _, subset := range setOfSubsets {
		var sb strings.Builder
		// 用分号作为分隔符，避免[12,3]和[1,23]这类歧义情况
		for i, num := range subset {
			if i > 0 {
				sb.WriteRune(';')
			}
			if _, err := sb.WriteString(strconv.Itoa(num)); err != nil {
				return fmt.Errorf("编码子集失败: %w", err)
			}
		}
		key := sb.String()
		if _, exists := seen[key]; exists {
			return fmt.Errorf("发现重复子集: %v", subset)
		}
		seen[key] = struct{}{}
	}
	return nil
}

实现2：哈希值+碰撞处理（性能更优） #

通过哈希函数将子集转为uint64哈希值，减少内存占用并提升速度，同时处理极低概率的哈希碰撞：

import (
	"fmt"
	"hash/fnv"
)

// 计算有序子集的哈希值
func subsetHash(subset []int) uint64 {
	h := fnv.New64a()
	for _, num := range subset {
		// 将int转为固定8字节二进制，确保不同整数的字节表示唯一
		b := [8]byte{}
		for i := 0; i < 8; i++ {
			b[i] = byte(num >> (uint(i) * 8))
		}
		h.Write(b[:])
	}
	return h.Sum64()
}

// 对比两个子集是否完全相等
func equal(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}
	for i := range a {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

func check(setOfSubsets [][]int) error {
	seen := make(map[uint64][][]int)
	for _, subset := range setOfSubsets {
		hashVal := subsetHash(subset)
		// 检查同哈希值的子集是否存在重复
		if existingSubsets, exists := seen[hashVal]; exists {
			for _, s := range existingSubsets {
				if equal(s, subset) {
					return fmt.Errorf("发现重复子集: %v", subset)
				}
			}
		}
		seen[hashVal] = append(seen[hashVal], subset)
	}
	return nil
}

方案二：排序后检查相邻元素 #

先对[][]int按自定义规则排序，再遍历检查相邻子集是否相等。此方法适合内存紧张但可接受排序开销的场景，但无法提前返回，必须完成排序后才能检测重复。

import (
	"fmt"
	"sort"
)

// 自定义子集排序规则：先比长度，长度相同则逐个元素比较
type subsetSlice [][]int

func (s subsetSlice) Len() int { return len(s) }
func (s subsetSlice) Less(i, j int) bool {
	a, b := s[i], s[j]
	minLen := len(a)
	if len(b) < minLen {
		minLen = len(b)
	}
	for k := 0; k < minLen; k++ {
		if a[k] != b[k] {
			return a[k] < b[k]
		}
	}
	// 元素全同时，长度短的排前面
	return len(a) < len(b)
}
func (s subsetSlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] }

func check(setOfSubsets [][]int) error {
	// 复制原切片避免修改输入数据
	subsets := make([][]int, len(setOfSubsets))
	copy(subsets, setOfSubsets)
	sort.Sort(subsetSlice(subsets))

	for i := 1; i < len(subsets); i++ {
		if equal(subsets[i-1], subsets[i]) {
			return fmt.Errorf("发现重复子集: %v", subsets[i])
		}
	}
	return nil
}

func equal(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}
	for i := range a {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

方案对比 #

根据你的需求（检测到第一个重复即返回），优先选择哈希表类方案，其中哈希值+碰撞处理的版本更适合百万级子集的高性能场景。

内容的提问来源于stack exchange，提问作者snow_abstraction