Golang：找到两个数字索引，其中这两个数字的总和等于目标数字

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 列表太长，我把它放在一个gist中：https : //gist.github.com/nickleeh/8eedb39e008da8b47864

这段代码工作正常，但我发现这return 0,0部分很难看，而且运行速度比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 个相等的索引，但这更方便（因为如果您忘记检查返回值并尝试使用无效索引，您将立即获得运行时恐慌，提醒您不要忘记检查返回值的有效性）。因此，在我的解决方案中，我将摆脱这种i + 1转变，因为它毫无意义。可以在答案末尾找到不同解决方案的基准测试。如果允许排序：如果切片很大并且没有变化，并且您必须twoSum()多次调用此函数，最有效的解决方案是sort.Ints()预先使用简单地对数字进行排序：sort.Ints(nums)然后您不必构建地图，您可以使用在sort.SearchInts()以下位置实现的二进制搜索：func twoSumSorted(nums []int, target int) (int, int) {&nbsp; &nbsp; for i, v := range nums {&nbsp; &nbsp; &nbsp; &nbsp; v2 := target - v&nbsp; &nbsp; &nbsp; &nbsp; if j := sort.SearchInts(nums, v2); v2 == nums[j] {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return i, j&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return -1, -1}注意：请注意，排序后，返回的索引将是排序切片中的值的索引。这可能与原始（未排序）切片中的索引不同（这可能是也可能不是问题）。如果您确实需要原始顺序（原始、未排序的切片）中的索引，您可以存储已排序和未排序的索引映射，以便获得原始索引。有关详细信息，请参阅此问题：golang排序后获取数组的索引如果不允许排序：这是您摆脱这种i + 1转变的解决方案，因为它毫无意义。切片和数组索引在所有语言中都为零。还利用for ... range：func twoSum(nums []int, target int) (int, int) {&nbsp; &nbsp; if len(nums) <= 1 {&nbsp; &nbsp; &nbsp; &nbsp; return -1, -1&nbsp; &nbsp; }&nbsp; &nbsp; m := make(map[int]int)&nbsp; &nbsp; for i, v := range nums {&nbsp; &nbsp; &nbsp; &nbsp; if j, ok := m[v]; ok {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return j, i&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; m[target-v] = i&nbsp; &nbsp; }&nbsp; &nbsp; return -1, -1}如果nums切片很大并且无法快速找到解决方案（意味着i索引变大），则意味着将向地图添加大量元素。地图开始时容量很小，如果需要额外的空间来承载许多元素（键值对），它们会在内部增长。内部增长需要使用已经添加的元素重新散列和重建。这是“非常”昂贵的。这看起来并不重要，但确实如此。由于您知道最终会出现在地图中的最大元素（最坏情况是len(nums)），因此您可以创建一个容量足够大的地图，以容纳最坏情况下的所有元素。好处是不需要内部增长和重新散列。您可以make()在创建map. twoSum2()如果nums很大，这会加快时间：func twoSum2(nums []int, target int) (int, int) {&nbsp; &nbsp; if len(nums) <= 1 {&nbsp; &nbsp; &nbsp; &nbsp; return -1, -1&nbsp; &nbsp; }&nbsp; &nbsp; m := make(map[int]int, len(nums))&nbsp; &nbsp; for i, v := range nums {&nbsp; &nbsp; &nbsp; &nbsp; if j, ok := m[v]; ok {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return j, i&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; m[target-v] = i&nbsp; &nbsp; }&nbsp; &nbsp; return -1, -1}基准测试这里有一个小基准码与输入的3个解决方案的测试执行的速度nums和target你提供的。请注意，为了测试twoSumSorted()，您首先必须对nums切片进行排序。将其保存到一个名为的文件中xx_test.go并使用以下命令运行它go test -bench .：package mainimport (&nbsp; &nbsp; "sort"&nbsp; &nbsp; "testing")func BenchmarkTwoSum(b *testing.B) {&nbsp; &nbsp; for i := 0; i < b.N; i++ {&nbsp; &nbsp; &nbsp; &nbsp; twoSum(nums, target)&nbsp; &nbsp; }}func BenchmarkTwoSum2(b *testing.B) {&nbsp; &nbsp; for i := 0; i < b.N; i++ {&nbsp; &nbsp; &nbsp; &nbsp; twoSum2(nums, target)&nbsp; &nbsp; }}func BenchmarkTwoSumSorted(b *testing.B) {&nbsp; &nbsp; sort.Ints(nums)&nbsp; &nbsp; b.ResetTimer()&nbsp; &nbsp; for i := 0; i < b.N; i++ {&nbsp; &nbsp; &nbsp; &nbsp; twoSumSorted(nums, target)&nbsp; &nbsp; }}输出：BenchmarkTwoSum-4&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1000&nbsp; &nbsp; &nbsp; &nbsp;1405542 ns/opBenchmarkTwoSum2-4&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;2000&nbsp; &nbsp; &nbsp; &nbsp; 722661 ns/opBenchmarkTwoSumSorted-4&nbsp; &nbsp; 10000000&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;133 ns/op如您所见，制作具有足够大容量的地图会加快速度：它的运行速度是原来的两倍。如前所述，如果nums可以提前排序，那就快了约 10,000倍！

Answer 2

如果nums总是排序，你可以做一个二分搜索，看看你所在的任何数字的补码是否也在切片中。func binary(haystack []int, needle, startsAt int) int {&nbsp; &nbsp; pivot := len(haystack) / 2&nbsp; &nbsp; switch {&nbsp; &nbsp; case haystack[pivot] == needle:&nbsp; &nbsp; &nbsp; &nbsp; return pivot + startsAt&nbsp; &nbsp; case len(haystack) <= 1:&nbsp; &nbsp; &nbsp; &nbsp; return -1&nbsp; &nbsp; case needle > haystack[pivot]:&nbsp; &nbsp; &nbsp; &nbsp; return binary(haystack[pivot+1:], needle, startsAt+pivot+1)&nbsp; &nbsp; case needle < haystack[pivot]:&nbsp; &nbsp; &nbsp; &nbsp; return binary(haystack[:pivot], needle, startsAt)&nbsp; &nbsp; }&nbsp; &nbsp; return -1 // code can never fall off here, but the compiler complains&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // if you don't have any returns out of conditionals.}func twoSum(nums []int, target int) (int, int) {&nbsp; &nbsp; for i, num := range nums {&nbsp; &nbsp; &nbsp; &nbsp; adjusted := target - num&nbsp; &nbsp; &nbsp; &nbsp; if j := binary(nums, adjusted, 0); j != -1 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return i, j&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return 0, 0}playground example或者您可以使用sort.SearchIntswhich 实现二进制搜索。func twoSum(nums []int, target int) (int, int) {&nbsp; &nbsp; for i, num := range nums {&nbsp; &nbsp; &nbsp; &nbsp; adjusted := target - num&nbsp; &nbsp; &nbsp; &nbsp; if j := sort.SearchInts(nums, adjusted); nums[j] == adjusted {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // sort.SearchInts returns the index where the searched number&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // would be if it was there. If it's not, then nums[j] != adjusted.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return i, j&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return 0, 0}