leetcode. twosum. 双层循环明显执行速度更快,只是时间复杂度高了,hash时间复杂度降低了,但是执行速度慢了。 为什么答案更倾向于hash?有大神解答吗?是我test数据问题?



func BenchmarkTwosum10001(t *testing.B) {
    t.Log("two sum target is 10001")
    for i := 0; i < t.N; i++ {
        //twoSum1(getData(), 19999)
        twoSum1(getData(), 10001)
    }
}

func BenchmarkTwosumMy10001(t *testing.B) {
    t.Log("two sum my target is 10001")

    for i := 0; i < t.N; i++ {
        //twoSumMy1(getData(), 19999)
        twoSumMy1(getData(), 10001)
    }
}

func BenchmarkTwosum19999(t *testing.B) {
    t.Log("two sum target is 19999")
    for i := 0; i < t.N; i++ {
        twoSum1(getData(), 19999)
        //twoSum1(getData(), 10001)
    }
}

func BenchmarkTwosumMy19999(t *testing.B) {
    t.Log("two sum my target is 19999")

    for i := 0; i < t.N; i++ {
        twoSumMy1(getData(), 19999)
        //twoSumMy1(getData(), 10001)
    }
}

func getData()[]int{
    d :=make([]int,10000)
    for i:=1;i<10000;i++{
        d[i]=i
    }
    return d
}

func twoSumMy1(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i]+nums[j] == target {
                return []int{nums[i], nums[j]}
            }
        }
    }
    return nil
}

func twoSum1(nums []int, target int) []int {
    hashMap := make(map[int]int,len(nums))
    for i, num := range nums {
        if index, ok := hashMap[num]; ok {
            return []int{index, i}
        } else {
            hashMap[target-num] = i
        }
    }
    return []int{}
}

以下是输出:

    192:main xianjinwang$ go test twoSum_test.go -bench=. -benchmem
    goos: darwin
    goarch: amd64
    BenchmarkTwosum10001-4              5000            271090 ns/op          401514 B/op          6 allocs/op
    --- BENCH: BenchmarkTwosum10001-4
            twoSum_test.go:19: two sum target is 10001
            twoSum_test.go:19: two sum target is 10001
            twoSum_test.go:19: two sum target is 10001
    BenchmarkTwosumMy10001-4           50000             28983 ns/op           81936 B/op          2 allocs/op
    --- BENCH: BenchmarkTwosumMy10001-4
            twoSum_test.go:27: two sum my target is 10001
            twoSum_test.go:27: two sum my target is 10001
            twoSum_test.go:27: two sum my target is 10001
            twoSum_test.go:27: two sum my target is 10001
    BenchmarkTwosum19999-4              3000            528345 ns/op          404178 B/op         12 allocs/op
    --- BENCH: BenchmarkTwosum19999-4
            twoSum_test.go:36: two sum target is 19999
            twoSum_test.go:36: two sum target is 19999
            twoSum_test.go:36: two sum target is 19999
    BenchmarkTwosumMy19999-4              50          28169564 ns/op           81941 B/op          1 allocs/op
    --- BENCH: BenchmarkTwosumMy19999-4
            twoSum_test.go:44: two sum my target is 19999
            twoSum_test.go:44: two sum my target is 19999
    PASS
    ok      command-line-arguments  6.235s

求解答,谢谢大家
已邀请:

zhangbitao

赞同来自:

你把数据规模放大10000倍再试试

heramerom

赞同来自:

貌似数据样本有点问题

func getData() []int {
    d := make([]int, 10000)
    for i := 1; i < 10000; i++ {
        d[i] = rand.Intn(100000)
    }
    return d
}

dragonbuf

赞同来自:

某种情况下,类似于 n^2 和 n 的区别

要回复问题请先登录注册