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

Question

问题是：找到两个数字的索引nums[index1] + nums[index2] == target。这是我的尝试golang（索引从 1 开始）：package mainimport (    "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/8eedb39e008da8b47864var target int = 16021func 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    endend

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) {

    for i, v := range nums {

        v2 := target - v

        if j := sort.SearchInts(nums, v2); v2 == nums[j] {

            return i, j

        }

    }

    return -1, -1

}

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

golang排序后获取数组的索引

如果不允许排序：

这是您摆脱这种i + 1转变的解决方案，因为它毫无意义。切片和数组索引在所有语言中都为零。还利用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切片很大并且无法快速找到解决方案（意味着i索引变大），则意味着将向地图添加大量元素。地图开始时容量很小，如果需要额外的空间来承载许多元素（键值对），它们会在内部增长。内部增长需要使用已经添加的元素重新散列和重建。这是“非常”昂贵的。

这看起来并不重要，但确实如此。由于您知道最终会出现在地图中的最大元素（最坏情况是len(nums)），因此您可以创建一个容量足够大的地图，以容纳最坏情况下的所有元素。好处是不需要内部增长和重新散列。您可以make()在创建map. twoSum2()如果nums很大，这会加快时间：

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切片进行排序。

将其保存到一个名为的文件中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

如您所见，制作具有足够大容量的地图会加快速度：它的运行速度是原来的两倍。

如前所述，如果nums可以提前排序，那就快了约 10,000倍！

Answer 2

如果nums总是排序，你可以做一个二分搜索，看看你所在的任何数字的补码是否也在切片中。

func binary(haystack []int, needle, startsAt int) int {

    pivot := len(haystack) / 2

    switch {

    case haystack[pivot] == needle:

        return pivot + startsAt

    case len(haystack) <= 1:

        return -1

    case needle > haystack[pivot]:

        return binary(haystack[pivot+1:], needle, startsAt+pivot+1)

    case needle < haystack[pivot]:

        return binary(haystack[:pivot], needle, startsAt)

    }

    return -1 // code can never fall off here, but the compiler complains

              // if you don't have any returns out of conditionals.

}

func twoSum(nums []int, target int) (int, int) {

    for i, num := range nums {

        adjusted := target - num

        if j := binary(nums, adjusted, 0); j != -1 {

            return i, j

        }

    }

    return 0, 0

}

playground example

或者您可以使用sort.SearchIntswhich 实现二进制搜索。

func twoSum(nums []int, target int) (int, int) {

    for i, num := range nums {

        adjusted := target - num

        if j := sort.SearchInts(nums, adjusted); nums[j] == adjusted {

            // sort.SearchInts returns the index where the searched number

            // would be if it was there. If it's not, then nums[j] != adjusted.

            return i, j

        }

    }

    return 0, 0

}