如何在O(n)中找到排序数组中给定数字和的两个数字？

Question

public static void findNumber(int number) {
    int[] soretedArray = { 1, 5, 6, 8, 9 };
    for (int i = 0; i <= soretedArray.length; i++) {
        for (int j = i + 1; j < soretedArray.length; j++) {
            if (soretedArray[i] + soretedArray[j] == number) {
                System.out.println(soretedArray[i] + "::" + soretedArray[j]);
                return;
            }
        }
    }
}

使用此代码,我能够找到数字,其复杂度为O(N ^ 2),但我必须使用O(N)复杂度来找到它,即在Java中只使用一个for循环或哈希映射或类似.

Answer 1

使用fixed number，对于数组中的任何选择，x您只需查找是否number-x在数组中（请注意，您也可以绑定x）。这不会给你 O(n)，而是 O(n.log(n))。

也许通过评论，如果你有a_i和a_j( j>i)，求和并与 进行比较number，如果结果更大，下一个有趣的测试是a_(i-1)或a_(j-1)，如果结果较低，下一个有趣的测试是a_(i+1)或a_(j+1)，会给出线性时间的提示吗？