Golang处理多级切片时遇到的奇怪重写问题

Golang处理多级切片时遇到的奇怪重写问题 大家好

我在处理 LeetCode 问题时，遇到了 Go 语言多层切片的一个奇怪现象。

我的基本算法应该是正确的， 但在使用多层切片时发生了一些奇怪的事情。

我知道这段代码可能冗长且乏味， 所以我添加了大量注释，真心希望能得到您的帮助！！！

提前非常感谢。

package main

import "fmt"

func main() {
	// 使用 nums 生成所有可能的子集
	// 例如：nums = [3, 5]
	// 子集 = [[], [3], [5], [3,5]]
	nums := []int{9, 0, 3, 5, 7}
	fmt.Println(subsets(nums))
}

// 这个算法应该是正确的：
// 我们使用动态规划，并将当前迭代的数字添加到
// 先前已存在的子集中
func subsets(nums []int) [][]int {
	if len(nums) == 0 {
		return nil
	}

	// 使用动态规划
	dp := make([][][]int, len(nums))
	dp[0] = [][]int{nil, {nums[0]}}

	// dp 迭代
	for i := 1; i < len(dp); i++ {
		dp[i] = dp[i-1]
		for _, v := range dp[i-1] {
			dp[i] = append(dp[i], append(v, nums[i]))
		}
	}

	// 返回最终结果
	return dp[len(dp)-1]
	// 然而，答案并不正确
}

// 正确的输出应该是：
// [[],[9],[0],[9,0],[3],[9,3],[0,3],[9,0,3],[5],[9,5],[0,5],[9,0,5],[3,5],
// [9,3,5],[0,3,5],**[9,0,3,5]**,[7],[9,7],[0,7],[9,0,7],[3,7],[9,3,7],
// [0,3,7],[9,0,3,7],[5,7],[9,5,7],[0,5,7],[9,0,5,7],[3,5,7],[9,3,5,7],[0,3,5,7],**[9,0,3,5,7]**]

// 我的答案是（注意 ** 标记的不同之处）：
// [[],[9],[0],[9,0],[3],[9,3],[0,3],[9,0,3],[5],[9,5],[0,5],[9,0,5],[3,5],
// [9,3,5],[0,3,5],**[9,0,3,7]**,[7],[9,7],[0,7],[9,0,7],[3,7],[9,3,7],
// [0,3,7],[9,0,3,7],[5,7],[9,5,7],[0,5,7],[9,0,5,7],[3,5,7],[9,3,5,7],[0,3,5,7],**[9,0,3,7,7]**]

// 这很奇怪
// 实际上，[9,0,3,5] 这个值最初被我的代码正确生成了
// 但在迭代中为现有结果追加 7 以生成 [9,0,3,7] 时，它被重写了

更多关于Golang处理多级切片时遇到的奇怪重写问题的实战教程也可以访问 https://www.itying.com/category-94-b0.html

2 回复

起初，我认为这可能是因为直接复制导致的

dp[i]=dp[i-1]

但在将其改为

// dp[i]=dp[i-1]
dp[i] = make([][]int, len(dp[i-1]))
copy(dp[i], dp[i-1])

后，它仍然不起作用

更多关于Golang处理多级切片时遇到的奇怪重写问题的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


问题出在切片共享底层数组导致的意外修改。当您使用 append(v, nums[i]) 时，如果 v 的容量足够容纳新元素，新切片会和原切片共享底层数组，导致 dp[i-1] 中的元素被意外修改。

以下是修复后的代码：

package main

import "fmt"

func subsets(nums []int) [][]int {
    if len(nums) == 0 {
        return [][]int{{}}
    }

    dp := make([][][]int, len(nums))
    dp[0] = [][]int{{}, {nums[0]}}

    for i := 1; i < len(nums); i++ {
        // 先复制 dp[i-1] 的所有元素
        dp[i] = make([][]int, len(dp[i-1]))
        for j := range dp[i-1] {
            dp[i][j] = make([]int, len(dp[i-1][j]))
            copy(dp[i][j], dp[i-1][j])
        }
        
        // 为每个现有子集添加当前数字
        for _, v := range dp[i-1] {
            newSubset := make([]int, len(v), len(v)+1)
            copy(newSubset, v)
            newSubset = append(newSubset, nums[i])
            dp[i] = append(dp[i], newSubset)
        }
    }

    return dp[len(dp)-1]
}

func main() {
    nums := []int{9, 0, 3, 5, 7}
    result := subsets(nums)
    fmt.Println(result)
}

更简洁的实现方式：

func subsets(nums []int) [][]int {
    result := [][]int{{}}
    
    for _, num := range nums {
        n := len(result)
        for i := 0; i < n; i++ {
            newSubset := make([]int, len(result[i]), len(result[i])+1)
            copy(newSubset, result[i])
            newSubset = append(newSubset, num)
            result = append(result, newSubset)
        }
    }
    
    return result
}

关键点在于每次创建新切片时都要显式复制底层数组，避免共享底层存储空间导致的意外修改。

回到顶部