arrays - 找到排序数组的索引，使得 a[i]+a[j]=x

Question

这是一道面试题:给定一个整数 x 和一个由 N 个不同整数组成的排序数组 a[]，设计一个线性时间算法 来确定是否存在两个不同的索引 i 和 j 使得 a[i] + a[j] == x。不允许辅助存储。我已经在 Java 中实现了它。但我当前的运行时间是 O(nlogn)，因为我在每次迭代 上执行了 binarySearch。所以它不是严格的线性。我想知道是否存在针对此问题的线性时间解决方案。如果是这样，关于它的一些指示可能会有所帮助。

谢谢。

public class SumArrayIndex {

    public static void main(String[] args){

        int[] arr={1,2,3,4,5,6,7,8,9,10};
        sumSortedArray(arr, 4);
        System.out.println();
        sumSortedArray(arr, 19);
        System.out.println();
        sumSortedArray(arr, 100);

    }

    public static void sumSortedArray(int[] arr, int sum){
        for (int i=0;i<arr.length;i++){
            int temp=Arrays.binarySearch(arr, sum-arr[i]);
            if (temp>0 && temp!=i){
                System.out.printf("The two indices are %s and %s%n ",i,temp);
                return;
            }
        }
        System.out.printf("The sum:%s cannot be formed with given array:%s",sum,Arrays.toString(arr));
    }
}

Answer 1

您可以根据以下观察将算法修改为线性时间:

1. 不失一般性，你可以说i和 j是这样的 arr[i]<arr[j] .证明:如果不是这样，你可以交换i和 j .
2. 考虑到你一开始就开始搜索，当你搜索sum-arr[i] , 您始终可以在索引 i 的右侧搜索;如果sum-arr[i] < arr[i] ，你知道没有答案，因为 j会在 i 的左边
3. 如果您之前搜索过 sum-arr[i]已在索引 k 处结束如果没有结果，您的下一次搜索可以在索引 i 之间进行和 k .
4. 您无需搜索 sum-arr[i]使用二进制搜索:你可以从后面进行线性搜索，并保持点 k其中 arr[k] < sum-arr[i]作为您的下一个起点。

这让您可以构建一个算法，对每个项目只检查一次。