记一个 golang 切片使用的坑

记一个 golang 切片使用的坑

tk_sky 84 2024-02-18

记一个 golang 切片使用的坑

今天在写 leetcode，做一道比较简单的题，看上去一个 dfs 就可以搞定：https://leetcode.cn/problems/combination-sum

然而交上去以后报了个奇怪的 WA：

4e7a40e02a7577e975a7d3dfe38d1575

鉴于其他 case 都是对的，只有一个答案莫名其妙错了一个数字，而且看我的逻辑，怎么都不应该把这个2写进答案里：

var ans [][]int

func dfs(candidates []int, target int, now []int, index int) {
    if target < 0 {
       return
    }
    for i := index; i < len(candidates); i++ {
       v := candidates[i]
       targetLeft := target - v
       if targetLeft == 0 {
          newNow := append(now, v)
          ans = append(ans, newNow)
          continue
       }
       if targetLeft < 0 {
          continue
       }
       newNow := append(now, v)
       dfs(candidates, targetLeft, newNow, i)
    }
}

func combinationSum(candidates []int, target int) [][]int {
    ans = make([][]int, 0)
    now := make([]int, 0)
    dfs(candidates, target, now, 0)
    return ans
}

于是开始用调试器 debug。需要注意，如果要查看栈外的全局变量，需要使用调试器的 evaluate 功能手动输入全局变量名。

在 append ans数组处打断点，发现对应答案 {3,3,3,3,3,3} 在 append 的时候成功加入了 ans 数组，而不是 {3,3,3,3,3,2}。

继续运行，发现在某一后续递归调用时刻，这个答案居然变成了{3,3,3,3,3,2}，但我的逻辑中除了加入的时候，不应该有机会修改已经加入了的 ans 的元素。

于是怀疑这里的切片操作在底层维度上有问题。经过排查，确认了这个问题就是由隐藏的对切片底层数组的修改导致的。

之前版本的核心逻辑，去掉dfs的递归，简化如下：

newNow := append(now, v)
ans = append(ans, newNow)
anotherNow := append(now, v2)

我们的目的是设一个比now多一个v的新数组，然后把这个数组加入 ans。同时，后续会有对now的其他 append操作。这里简化了递归传递dfs(candidates, targetLeft, newNow, i)，虽然传了一个新的切片newNow，但这个新的切片也是原来 now 一样的底层数组的引用，所以这里就可以简化为 now。在编写时没有考虑到这一点，所以主观认为在递归时传递了一个新的独立的数组，从而导致后续的问题。

我们知道，golang 的切片是对底层数组的封装，主要维护长度和容量两个属性。在基于一个切片创建新的切片时，runtime 会根据容量是否满足操作需求来决定是沿用同一个底层数组，还是建一个新的。也就是说，使用 append 追加元素时，根据容量，有可能使用同一个数组，也有可能新建一个；而截取子切片时，就不会创建新的底层数组。如果底层数组是同一个，那么修改一个其切片，关联的切片也会受到影响。

最重要的是要理解切片的 struct 本身虽然是值传递，但切片实际表示了数组的引用传递。因此，在明确需要修改时，应当使用传值的方法 copy 一份数据到新切片，而不是直接用 append 或裁剪子切片的方式。

上述代码第一句修改为：

newNow := make([]int,len(now))
copy(newNow, now)
newNow = append(newNow, v)

顺利 ac。

总之要注意，在数据需要相对持久的保存的时候，就需要考虑所有与该切片相关的切片可不可能被隐式或显式的修改。在这个case里，就是在回溯到上一个节点的时候，对 now 进行了重新 append，导致修改到了和储存在答案中的切片的同一个底层数组中的元素。如果有修改的可能，果断用 copy 函数拷贝一份新的。

golang