这个 2sum 算法 O(nlogn) 怎么样？

Question

给定一个列表 L 和一个整数 c，我必须找出列表中是否有两个元素加起来等于 c（2Sum 问题）。我想出了以下算法：

def tsum(L,c):
    a=sorted(L)
    b=sorted(L,reverse=True)
    for kleineZahl in a:
        for großeZahl in b:
            sum=kleineZahl+großeZahl
            if sum>c:
                continue
            elif sum==c:
                return(True)
            elif sum<c:
                break
return(False)

现在我发现它在 O(n log n) 中运行，因为排序需要 O(n log n)动作。 "scanning" 应该采取 O(n) 操作。怎么来的？

我认为最坏的情况是 L=[1,1,1,1,1,c,c,c,c,c]。 runtime怎么不是n/2*n/2，所以O(n²)?

Answer 1

你上面讨论的算法确实有O(n²)的时间复杂度。其实这里不需要先对元素进行排序。然而，您可以实现一个更聪明的方法：首先对列表进行排序，然后维护两个指针：left 和 right。 right 从列表的 right 移动到 left，并且约束始终保持 a[left]+a[right] >= sum。如果你命中，你 return True，如果 left 超过 right，我们知道不存在这样的命中，我们 return False，由于最多left和right执行O(n)步，时间复杂度为O(n)，但排序步骤使其成为 O(n log n)。因此，更聪明的算法是：

def tsum(L,c):
    a=sorted(L)
    left = 0
    right = len(L)-1
    while left < right:
        right1 = right
        while a[left]+a[right1] > c:
            right1 -= 1
        if a[left]+a[right1] == c:
            return True
        elif right1 < right:
            right = right1+1
        left += 1
return False

不同之处在于，您不必检查从远-右到数组中的某个点，您可以简单地从上一次迭代结束的地方开始。

Answer 2

您可以通过完全删除内部循环来使其复杂化。我将依赖基础数学和哈希图（字典）。请注意，hashmap 搜索应该在常数时间 O(1)

内发生

下面的代码是用 Swift 编写的，但您可以轻松地将其翻译成 Python。请注意，它 returns 所有元素的索引，其总和等于 'sum':

func findTwoSum(_ array: [Int], sum: Int) -> [(Int, Int)] {
    var result = [(Int, Int)]()

    var diffs = Dictionary<Int, Int>()

    for i in 0..<array.count {
        let val = array[i]

        // if the number is already in the dict, we've found the pair
        // since diff + val == sum
        let diff = sum - val
        if let foundIndex = diffs[diff]  {
            result.append(contentsOf: [(foundIndex, i), (i, foundIndex)])
        } else {
            // store the value in the dict
            diffs[val] = i
        }            
    }

    return result
}

这个 2sum 算法 O(nlogn) 怎么样？

How is this 2sum Algorithm O(nlogn)?

python

runtime

time-complexity

这个 2su​​m 算法 O(nlogn) 怎么样？

How is this 2sum Algorithm O(nlogn)?

python

runtime

time-complexity

这个 2sum 算法 O(nlogn) 怎么样？