java - 查找整数是否为整数之和之一的有效方法

Question

这是一项学校作业，但是，要求是该程序“以最高性能实现” - 这对我来说很模糊，因为我不知道内存是否会超过速度等。但我正在寻找的是是否有一种“棘手”的方法通过对输入数据进行一些智能操作来解决问题。

所以，问题来了:假设你有两个数组，A 和 B，编写一个函数，如果 B 中有这样的整数，则返回 1，该整数等于 A 的任何两个后续元素的总和。

下面是我的文章。请注意，我没有使用 Hashmap<Integer>因为我认为加速所需的内存是一个缺点，足以承受 O(n * m) 速度作为我最坏的情况，而不是 O(n)。

public static int arrayContainsSum(int[] a, int[] b)
{
    int offsetA = a.length - 1;
    int offsetB = offsetA;
    int index = b.length - 1;
    int result = 0;
    int tested;

    while (index >= 0)
    {
        if (offsetA > 0) a[offsetA] += a[--offsetA];
        else if (offsetA == 0) // This has a danger of overflowing the int
            a[offsetA--] = multiply(a);
        tested = b[index];
        if ((offsetA < 0 && tested != 0 && a[0] % tested != 0) ||
            offsetB == 0)
        {
            // No point to test this element as it doesn't 
            //divide the product of sums
            offsetB = a.length - 1;
            index--;
        }
        if (tested == a[offsetB--])
        {
            result = 1;
            break;
        }
    }
    return result;
}

private static int multiply(int[] input)
{
    int accumulator = input.length > 0 ? 1 : 0;
    for (int i : input)
        if (i != 0) accumulator *= i;
    return accumulator;
}

有些事情我不关心:整数溢出(这可能是乘法的结果)。我假设array.length与读取局部变量一样快。

但是，我的问题是“难道不能通过分析来解决这个问题吗？”这意味着更高的效率？

PS。问题没有提到数组是否只包含唯一成员 - 对此没有限制。我还认为可以通过排序 a 来优化(如果我检测到这种情况)这样万一 b[x]小于 a 中的最小元素或大于 a 中的最大元素，它会节省一些查找 - 但是，这又会以增加复杂性为代价，可能并不完全合理。

Answer 1

public static int arrayContainsSum(int[] a, int[] b) {
  final Set<Integer> sums = new HashSet<Integer>();
  for (int i = 0; i < a.length - 1; i++) sums.add(a[i] + a[i+1]);
  for (int x : b) if (sums.contains(x)) return 1;
  return 0;
}