记一个 golang 切片使用的坑

记一个 golang 切片使用的坑

tk_sky 65 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 函数拷贝一份新的。