performance - 戈朗 : Find two number index where the sum of these two numbers equals to target number

Question

问题是:找到 nums[index1] + nums[index2] == target 两个数字的索引。这是我在 golang 中的尝试(索引从 1 开始):

package main

import (
    "fmt"
)

var nums = []int{0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 25182, 25184, 25186, 25188, 25190, 25192, 25194, 25196} // The number list is too long, I put the whole numbers in a gist: https://gist.github.com/nickleeh/8eedb39e008da8b47864
var target int = 16021

func twoSum(nums []int, target int) (int, int) {
    if len(nums) <= 1 {
        return 0, 0
    }
    hdict := make(map[int]int)
    for i := 1; i < len(nums); i++ {
        if val, ok := hdict[nums[i+1]]; ok {
            return val, i + 1
        } else {
            hdict[target-nums[i+1]] = i + 1
        }
    }
    return 0, 0
}

func main() {
    fmt.Println(twoSum(nums, target))
}

nums 列表太长了，我把它归为一个要点: https://gist.github.com/nickleeh/8eedb39e008da8b47864

这段代码工作正常，但我发现 return 0,0 部分很难看，而且它的运行速度比 Julia 翻译慢十倍。我想知道有没有写的很烂影响性能的部分？

编辑:Julia 的翻译:

function two_sum(nums, target)
    if length(nums) <= 1
        return false
    end
    hdict = Dict()
    for i in 1:length(nums)
        if haskey(hdict, nums[i])
            return [hdict[nums[i]], i]
        else
            hdict[target - nums[i]] = i
        end
    end
end

Answer 1

在我看来，如果没有找到添加到 target 的元素，最好是返回无效索引的值，例如-1。尽管返回 0, 0 就足够了，因为有效的索引对不能是 2 个相等的索引，但这更方便(因为如果您忘记检查返回值并尝试使用无效的索引，你会立即得到一个运行时 panic ，提醒你不要忘记检查返回值的有效性)。因此，在我的解决方案中，我将摆脱 i + 1 转变，因为它没有意义。

在答案末尾可以找到不同解决方案的基准。

如果允许排序:

如果 slice 很大且不变，并且您必须多次调用此 twoSum() 函数，最有效的解决方案是简单地使用 sort.Ints() 对数字进行排序。提前:

sort.Ints(nums)

然后你不必构建 map ，你可以使用在sort.SearchInts()中实现的二进制搜索。 :

func twoSumSorted(nums []int, target int) (int, int) {
    for i, v := range nums {
        v2 := target - v
        if j := sort.SearchInts(nums, v2); v2 == nums[j] {
            return i, j
        }
    }
    return -1, -1
}

注意:请注意，排序后，返回的索引将是已排序 slice 中值的索引。这可能与原始(未排序的) slice 中的索引不同(这可能是也可能不是问题)。如果您确实需要原始顺序(原始的、未排序的 slice )的索引，您可以存储已排序和未排序的索引映射，以便您可以获得原始索引。有关详细信息，请参阅此问题:

Get the indices of the array after sorting in golang

如果不允许排序:

这是您摆脱 i + 1 转变的解决方案，因为它毫无意义。 slice 和数组索引在所有语言中都是从零开始的。还利用 for ... range:

func twoSum(nums []int, target int) (int, int) {
    if len(nums) <= 1 {
        return -1, -1
    }
    m := make(map[int]int)
    for i, v := range nums {
        if j, ok := m[v]; ok {
            return j, i
        } 
        m[target-v] = i
    }
    return -1, -1
}

如果 nums slice 很大并且没有快速找到解决方案(意味着 i 索引变大)这意味着很多元素将被添加到 map 中. map 从小容量开始，如果需要额外空间来容纳许多元素(键值对)，它们会在内部增长。内部增长需要使用已经添加的元素重新散列和重建。这是“非常”昂贵的。

它看起来并不重要，但它确实很重要。由于您知道最终将出现在 map 中的最大元素(最坏情况是 len(nums))，因此您可以创建一个容量足够大的 map 来容纳最坏情况下的所有元素。好处是不需要内部增长和重新散列。创建 map 时，您可以将初始容量作为第二个参数提供给 make()。如果 nums 很大，这会大大加快 twoSum2() 的速度:

func twoSum2(nums []int, target int) (int, int) {
    if len(nums) <= 1 {
        return -1, -1
    }
    m := make(map[int]int, len(nums))
    for i, v := range nums {
        if j, ok := m[v]; ok {
            return j, i
        }
        m[target-v] = i
    }
    return -1, -1
}

基准测试

这里有一些基准测试代码，用于测试 3 个解决方案的执行速度，其中包含您提供的输入 nums 和 target。请注意，为了测试 twoSumSorted()，您首先必须对 nums slice 进行排序。

将其保存到名为 xx_test.go 的文件中，然后使用 go test -bench 运行它。:

package main

import (
    "sort"
    "testing"
)

func BenchmarkTwoSum(b *testing.B) {
    for i := 0; i < b.N; i++ {
        twoSum(nums, target)
    }
}

func BenchmarkTwoSum2(b *testing.B) {
    for i := 0; i < b.N; i++ {
        twoSum2(nums, target)
    }
}

func BenchmarkTwoSumSorted(b *testing.B) {
    sort.Ints(nums)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        twoSumSorted(nums, target)
    }
}

输出:

BenchmarkTwoSum-4              1000       1405542 ns/op
BenchmarkTwoSum2-4             2000        722661 ns/op
BenchmarkTwoSumSorted-4    10000000           133 ns/op

如您所见，制作容量足够大的 map 会加快速度:它的运行速度是两倍。

如前所述，如果 nums 可以提前排序，那就是 ~10,000 倍!