将数组附加到矩阵时的奇怪行为

Question

我错过了一些关于切片的基本内容，导致我的结果最终看起来很奇怪。是的，这是来自利特代码的问题。我用它来学习围棋，因为我发现用新语言解决算法对我很有帮助。我不需要算法的答案，也不需要知道如何修复算法。我只想知道为什么当我附加另一个值时，我的附加值会发生变化。首先，这是我的代码：type node struct {    value int    children []*node}func combinationSum(candidates []int, target int) [][]int {        var output [][]int        var acc []int        combinationSum2(candidates, &output, target, acc, 0)        return output}func combinationSum2(candidates []int, output *[][]int, target int, acc []int, sum int) {        if(sum == target) {        fmt.Println(acc)        *output = append(*output, acc)        fmt.Println(output)        return    }        if(sum > target) {        return    }        for i := 0; i < len(candidates); i++ {        combinationSum2(candidates[i:], output, target, append(acc, candidates[i]), sum + candidates[i])    }    }我正在测试这个代码，候选者=[2，3，5]和目标=8正确的输出应该是[[2，2，2，2]，[2，3，3]，[3，5]];但是，我的代码返回 [[2，2，2，5]，[2，3，3]，[3，5]]有趣的是，当我记录if语句中的 acc 值和追加 acc 值后的输出时，似乎我追加的值在追加第二个数组后发生了变化。acc = [2 2 2 2]output = &[[2 2 2 2]]acc = [2 3 3]output = &[[2 2 2 5] [2 3 3]]acc = [3 5]output = &[[2 2 2 5] [2 3 3] [3 5]]我尝试在本地运行它，并得到同样的奇怪行为。这是什么原因造成的？

Answer 1

正如我在注释中所写的那样，原始代码中的问题是函数中的追加用法。用于传递电流扩展的电流到方法。我已向此函数添加了更多日志记录combinationSum2appendacccandidatecombinationSum2

func combinationSum2(candidates []int, output *[][]int, target int, acc []int, sum int) {

    if sum == target {

        fmt.Println("Acc:", acc)

        *output = append(*output, acc)

        fmt.Println("Output:", output)

        return

    }

    if sum > target {

        return

    }

    for i := 0; i < len(candidates); i++ {

        extendedAcc := append(acc, candidates[i])

        fmt.Printf("Extended: %v %p\n", extendedAcc, extendedAcc)

        combinationSum2(candidates[i:], output, target, extendedAcc, sum+candidates[i])

    }

}

并收到以下结果（这只是前几行有趣的几行）

Extended: [2] 0x14000130008

Extended: [2 2] 0x14000130030

Extended: [2 2 2] 0x1400013c020

Extended: [2 2 2 2] 0x1400013c020

Acc: [2 2 2 2]

Output: &[[2 2 2 2]]

Extended: [2 2 2 3] 0x1400013c020

Extended: [2 2 2 5] 0x1400013c020

Extended: [2 2 3] 0x1400013c040

Extended: [2 2 3 3] 0x1400013c040

如您所见，变量在被添加到后仍然具有相同的地址（它们在值之后打印为十六进制）。此地址的最终值是您在 中看到的值。它不是的原因是附加如何在内部工作的结果。如果当前数组中没有足够的空间，它会创建一个新的数组并向其返回一个切片。当您比较 slice 的地址时，此行为是可见的。extendedAccOutput[2 2 2 5]Output[2 2 3 3]extended

这是正常工作的解决方案：

package main

import "fmt"

type node struct {

    value    int

    children []*node

}

func combinationSum(candidates []int, target int) [][]int {

    var output [][]int

    var acc []int

    combinationSum2(candidates, &output, target, acc, 0)

    return output

}

func combinationSum2(candidates []int, output *[][]int, target int, acc []int, sum int) {

    if sum == target {

        fmt.Println(acc)

        *output = append(*output, acc)

        fmt.Println(output)

        return

    }

    if sum > target {

        return

    }

    for i := 0; i < len(candidates); i++ {

        currentAcc := make([]int, 0, len(acc) + 1)

        currentAcc = append(currentAcc, acc...)

        currentAcc = append(currentAcc, candidates[i])

        combinationSum2(candidates[i:], output, target, currentAcc, sum+candidates[i])

    }

}

func main() {

    combinationSum([]int{2, 3, 5}, 8)

}

或者，该函数可能如下所示：combinationSum2

func combinationSum2(candidates []int, output *[][]int, target int, acc []int, sum int) {

    if sum == target {

        fmt.Println(acc)

        accCopy := make([]int, 0, len(acc))

        accCopy = append(accCopy, acc...)

        *output = append(*output, accCopy)

        fmt.Println(output)

        return

    }

    if sum > target {

        return

    }

    for i := 0; i < len(candidates); i++ {

        combinationSum2(candidates[i:], output, target, append(acc, candidates[i]), sum+candidates[i])

    }

}

在我看来，这通常不太安全，但可以很好地解决这个问题。