查找两个数组之间的重复值

Question

假设我有以下两个数组：

 int[] a = [1,2,3,4,5];
int[] b = [8,1,3,9,4];

我想取数组的第一个值 a - 1 - 看看它是否包含在数组 b 中。所以，我会得到 a 中的“1”在 b 即使它不在同一个位置。一旦我完成了对 a 中第一个元素的比较，我就转到数组中的下一个数字 a 并继续这个过程，直到我完全完成第一个数组。

我知道我需要做一些循环（可能是嵌套的？）但我不太明白我是如何坚持数组中的第一个数字 a 同时遍历数组中的所有数字 b 。

这似乎很简单，我只是无法理解它……

原文由 user1076802 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这些解决方案都需要 O(n^2) 时间。您应该利用哈希图/哈希集来获得更快的 O(n) 解决方案：

 void findDupes(int[] a, int[] b) {
    HashSet<Integer> map = new HashSet<Integer>();
    for (int i : a)
        map.add(i);
    for (int i : b) {
        if (map.contains(i))
            // found duplicate!
    }
}

原文由 erikreed 发布，翻译遵循 CC BY-SA 3.0 许可协议