当前位置： > > > > 二数和算法

二数和算法

来源：stackoverflow
2024-04-30 11:54:24
0浏览
收藏

珍惜时间，勤奋学习！今天给大家带来《二数和算法》，正文内容主要涉及到等等，如果你正在学习Golang，或者是对Golang有疑问，欢迎大家关注我！后面我会持续更新相关内容的，希望都能帮到正在学习的大家！

问题内容

下面算法的时间复杂度是 o(log(n))，但我只是好奇 for 循环的时间复杂度是多少？

func TwoNumberSum(array[] int, target int)[] int {
    sort.Ints(array)
    left, right: = 0, len(array) - 1
    for left < right && left >= 0 && right < len(array) {
        if array[left] + array[right] == target {
            return [] int {
                array[left], array[right]
            }
        } else if array[left] + array[right] < target {
            left += 1
        } else {
            right -= 1
        }
    }
    return [] int {}
}

正确答案

该声明不正确。对于 input = [1,2,3,4,5] 且 target = 9，left 将遍历整个数组。 for 循环以及整个算法的复杂度为 O(n)。

编辑：我刚刚注意到额外的 sort() 调用。排序会使算法的复杂度为O(nlogn)。

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持米云！更多关于Golang的相关知识，也可关注米云公众号。