在不到O(n ^ 2)的时间内比较两个数组的元素? [英] Compare elements of two arrays in less than O(n^2) time?

问题描述

我有两个整数数组.我需要找出两个数字，每个数组中的一个数字之和等于2.这在O(n ^ 2)中非常简单，但是有一种更快的方法吗?

I have two integer arrays. I need to find out two numbers, one from each array, whose sum is equal to 2. This is very simple in O(n^2) but is there a way to do it faster?

推荐答案

您可以在O(N + M)时间和O(N)空间中执行以下操作:

You can do it in O(N+M) time and O(N) space like this:

• 将数组 a 的元素放入哈希集中
• 遍历数组 b ，并检查哈希表是否包含 2-b [i]

• Put elements of array a into a hash set
• Walk through array b, and check if hash table contains 2-b[i]

构造一个 N 个元素的哈希集需要O(N)时间和O(N)空间.对照散列集检查每个 M 个元素需要O(1)，总共O(N + M)时间.

Constructing a hash set of N elements takes O(N) time and O(N) space. Checking each of M elements against the hash set takes O(1), for a total of O(N+M) time.

这篇关于在不到O(n ^ 2)的时间内比较两个数组的元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！