韩槑槑

Go 刷题中不小心踩过的坑(切片)

字数统计: 564阅读时长: 2 min
2018/11/09 Share

起因

这是一个我在刷算法题的时候遇到的问题,困了我一个下午没想出来是为什么。
题目:子集

这是我出现问题的那版代码
可以明显的发现红框的两个地方其实是一个 leftArr ,但是在经过一次函数调用后就被修改了

分析为什么会这样

为什么会出现这种情况呢?

让我们来分析一下代码,其实 search 函数是一个 前序遍历 ,内部有两个递归函数
所以 search 函数一开始会先执行第 19 行一直递归到 index == len(nums)
也就是 index = 5 时返回最后的 temp = [0, 3, 5, 7, 9]
既然代码的报错处 index = 3,我们就可以先从此时开始分析(画了个图方便看)

  • index = 3 时,temp = [0, 3, 5](先是一直走 leftArr 所以 temp 包含了前面的所有值)
  • 首先继续走 leftArr ,此时 temp = [0, 3, 5, 7],因为最上面的结果图显示是第四个值被改变了,此时第四个值已经存在,所以 index = 4 之后可以不被考虑
  • 然后返回 index = 3,走 rightArr,此时 temp = [0, 3, 5],第四个索引处没有值
  • 最后再走 leftArr 时,num[4] = 9 赋值给了此时 temp 的第四个索引处导致 temp = [0, 3, 5, 9]

结论

  • 由于 Go 的扩容机制,会导致切片容量翻倍(在 cap 小于 1024 的时候是翻倍,超出 1024 的时候是 * 1.25),具体可以参考源码slice.go
  • 所以当 index = 3 时,虽然 len(temp) == 3,但是 cap(temp) == 4
  • 最终其实这道题的坑就是 temp 第四个索引被赋值了两次导致第一次的值被修改(虽然 Go 是值传递,但是切片内部的地址是引用)
  • 可以看下这篇帖子了解下扩容:https://studygolang.com/articles/16052?fr=sidebar

最后再看下各个时期的 temp


可以发现,虽然 temp 长度只有 3,但是 cap 却已经有 4
这就导致地址 temp[3] 的地址早已被分配,之后没对 temp[3] 做一次修改都会影响到之前的结果。
真的是头很痛啊,所以 slice 一定要谨慎呀。

CATALOG
  1. 1. 起因
  2. 2. 分析为什么会这样
  3. 3. 结论
  4. 4. 最后再看下各个时期的 temp 吧