在未排序的数组中查找值

Question

我需要找出数组中任意两个数字之和的所有组合。如果相等则打印它们。 该问题的线性解的复杂度为 O(N^2)。 我想到了排序然后进行二进制比较。复杂度仍然是 (NlogN + N)

问题是我需要找到它的所有组合。

这个问题的线性解 例如。

//Linear search, find all the combinations
Find(int a[], int Target)
    {
       for(i=0; i<arr_size; i++)
            for(j=0; j<arr_size; j++)
                if((a[i]+a[j]) == Target)
                     cout<<a[i]<<a[j]
     }

有什么办法可以进一步降低复杂度吗？

谢谢， 大师

Answer 1

你可以先过滤掉所有不可能的事情。这应该只需要对数组进行两次迭代，并且有可能显着减少集合。如果没有，那么你只损失了 2 次迭代。

对于初学者，您可以找到最小的数字，然后过滤掉所有值 > （目标 - 最少数量）。

Answer 2

性能略有提高

private static void find(int[] a, int target) {

    for (int i = 0; i < a.length; i++) {
        if (a[i] == target) {
            System.out.println("result found");
            break;
        }
        if (a[i] > target) {
            break;
        }
        for (int j = 0; j < a.length; j++) {
            if ((i != j && (a[i] + a[j]) == target)) {
                System.out.println("result found");
            }
        }
    }
}