前几天，我接受了亚马逊的采访，他们问我一个问题，涉及以下问题。

给定2个整数数组，其中包含任意数量的正负元素，请查找出现在两个数组中的数字。

我能够非常轻松地解决此问题，HashMaps因此它将具有O(n)计算复杂性，但是不幸的是，这还将具有O(n)空间复杂性。可以通过遍历每个数组中的所有元素而无需额外的内存来完成此操作，但这将是O(n^2)。

在我解释完该HashMap方法之后，面试官问我是否可以想到一种在计算上为O（n）但不会使用任何额外内存的方法。我想不出任何动态，也无法为此找到解决方案。有没有一种方法可以在线性时间内不使用额外的内存来查找这些值？

注意：我已经在CareerCup上发布了这个问题，但是那里的每个人似乎都没有得到这样的概念，即我不需要使用它来占用额外的空间，并且必须在O(n)计算上使用它。

这是我在面试中使用的代码。它可以工作，但是空间不是O（1）。

import java.util.*;
public class ArrayFun {
    public static void main(String[] args) {

        int[] a = {1,2,3,4};
        int[] b = {2,5,6,7,3,2,2,2,2,1,2,2,2,2};
        ArrayList<Integer> matches = ArrayFun.findMatches(a,b);
        for (int i = 0;i<matches.size();++i) {
            System.out.println(matches.get(i));
        }
    }

    public static ArrayList<Integer> findMatches(int[] a, int[] b) {
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        ArrayList<Integer> matches = new ArrayList<Integer>();
        for (int i = 0;i<a.length;++i) {
            map.put(a[i],0);
        }
        for (int i = 0;i<b.length;++i) {
            if (map.get(b[i]) != null && map.get(b[i]) == 0) {
                map.put(b[i],1);
                matches.add(b[i]);
            }
        }
        return matches;
    }
}

此代码将返回

1,2,3

编辑：同样，当我说没有额外的空间和O（1）时，我有点可以互换使用它们。没有多余的空间，我是说较小的占位符变量很好，但分配新数组则不行。