Python：改善运行时间：选择两个movie_lengths，其total_untimes将等于确切的飞行长度

Question

我正在解决另一个面试问题，它是关于以下编码面试问题。

所以我正在构建一个功能来选择两部电影，其总运行时间将等于确切的飞行长度。

问题如下：编写一个函数，接受一个整数 flight_length（以分钟为单位）和一个整数列表 movie_lengths（以分钟为单位）和 returns 一个布尔值，指示 movie_lengths 中是否有两个数字总和等于 flight_length.

我首先想到我们可以通过嵌套两个循环来完成（外层选择first_movie_length，内层选择second_movie_length）。这会给我们 O(n^2)O(n2)

的运行时间

但我们有没有可能做得更好？

我有以下解决方案：

  def can_two_movies_fill_flight(movie_lengths, flight_length):

# movie lengths we've seen so far
movie_lengths_seen = set()

for first_movie_length in movie_lengths:

    matching_second_movie_length = flight_length - first_movie_length
    if matching_second_movie_length in movie_lengths_seen:
        return True

    movie_lengths_seen.add(first_movie_length)

# we never found a match, so return False
return False

我认为这个解决方案给了我 O(n) 时间，O(n) O(n) space。

我可以使用哈希映射吗？

Answer 1

我们可以先对 movie_lengths 进行排序——然后我们可以使用二进制搜索在 O(\lg{n})O(lgn) 时间而不是 O(n)O 中找到 second_movie_length (n) 时间。但是排序会花费 O(nlg(n))O(nlg(n))，我们可以做得更好。

我的解决方案：使用集合作为我们的数据结构。我们通过 movie_lengths 进行一次遍历，将每个项目视为 first_movie_length。在每次迭代中。

看看是否有匹配的_second_movie_length 我们已经看到（存储在我们的 movie_lengths_seen 集合中）等于 flight_length - first_movie_length。如果有，我们短路并 return True。通过输入当前的 first_movie_length.

使我们的 movie_lengths_seen 设置保持最新

  def can_two_movies_fill_flight(movie_lengths, flight_length):

    # movie lengths we&#39;ve seen so far
    movie_lengths_seen = set()

    for first_movie_length in movie_lengths:

        matching_second_movie_length = flight_length - first_movie_length
        if matching_second_movie_length in movie_lengths_seen:
            return True

        movie_lengths_seen.add(first_movie_length)

    return False

我们知道用户不会看同一部电影两次，因为我们会在放入 first_movie_length 之前检查 movie_lengths_seen 是否匹配_second_movie_length！

效率和算法复杂度：O(n)O(n) 时间，O(n)O(n) space。请注意，在优化运行时时，我们增加了一些 space 成本。

Python：改善运行时间：选择两个movie_lengths，其total_untimes将等于确切的飞行长度

Python: Improving run-time: Choosing two movie_lengths whose total_untimes will equal the exact flight length

python

runtime