Geek asks and answers

Find the indices of the sorted array so that a [i] + a [j] = x

This is an interview question: with integer xand take into account sorted array a[] of N distinct integersa linear-time algorithmto determine if there are two different indices i and j such that a[i] + a[j] == x. Additional storage is not allowed. I implemented this in Java. but my current work time O(nlogn)is because I'm doing binarySearchon each iteration. so it’s not strict linear. I am wondering if there is any for this problem linear time solution. If so, some pointers to it may be useful.

Thank.

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));
    }
}
+3
source share
2 answers

@leif , array, , . index, sum. , . - .

:

public static void sumSortedArray2(int[] arr, int sum){
        boolean found=false;
        int max=arr.length-1;
        int min=0;
        while (min<max){
            if(arr[min]+arr[max]<sum)
                min++;
          else if (arr[min]+arr[max]>sum)
                max--;
          else {
              found =true;
              break;
          }
    }
    if (found){
        System.out.printf("The two indices are %s and %s%n ",min,max);
    }
    else {
        System.out.printf("The sum:%s cannot be formed with given array:%s",sum,Arrays.toString(arr));
    }
}
0

, :

  • , , i j , arr[i]<arr[j]. . , i j.
  • , , sum-arr[i] i; sum-arr[i] < arr[i], , , j i
  • sum-arr[i] k , i k.
  • sum-arr[i] : k arr[k] < sum-arr[i] .

, .

+2

More articles:


All Articles