在O(n*log(n))中找到具有给定总和和乘积的一对数组元素

Question

设A是n个正整数的数组,并且给定整数.

我正在寻找算法来查找数组中是否有一对元素, A[i] * A[j] == k以及A[i] == A[j] + k.如果有这样的一对,算法应该返回它们的索引.

这是一项家庭作业,我们被告知有一个O(n*log(n))解决方案.

Answer 1

这是 Graphics Noob 的解决方案，有些澄清。

而且，它更像是 O(N)（假设哈希不会让我们失败），而不是 O(N*log(N))。

Result findMultiplicationIndices(int[] A, int[] B, int k)
{
    HashMap<Integer,Integer> aDivisors = new HashMap<Integer,Integer>();
    for(int i=0;i<A.length;i++)
    {
        int a = A[i];
        if(a!=0)
        {
            int d = k/a;
            if(d*a == k) 
                aDivisors.put(d, i);
        }
    }
    for(int i=0;i<B.length;i++)
    {
        Integer ai = aDivisors.get(B[i]);
        if(ai != null)
            return new Result(ai, i);
    }
    return null;
}