java - 如何根据条件查找数组中数字的索引位置？

Question

我有一个整数数组.. 我将输入一个数字 我必须找出两个数字的索引位置，以便数字之和 等于输入的数字。

我用下面的代码做到了

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class FindIndex {

    int a[] = { 1, 7, 6, 5, 12, 2, 3, 11 };

public void findingIndex() {
    Arrays.sort(a);
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the sum of two selected numbers from the array");
    int i = sc.nextInt();
    for(int j=0;j<a.length;j++){
        for(int k=j+1;k<a.length;k++){
            if(a[j]+a[k]==i){
                System.out.println(Arrays.toString(a));
                System.out.println("The indexes of the elements are"+j+"and"+k);
            }
        }
    }


}

public static void main(String[] args) {
    FindIndex fi = new FindIndex();
    fi.findingIndex();
    System.out.println("end of the program");
}

}

输出为

Enter the sum of two selected numbers from the array
14
[1, 2, 3, 5, 6, 7, 11, 12]
The indexes of the elements are1and7
[1, 2, 3, 5, 6, 7, 11, 12]
The indexes of the elements are2and6
end of the program

现在我想仅使用一个 for 循环来实现这一点？该怎么做？

Answer 1

你可以用这种方式在 O(n * log n) 时间内完成。

public static int[] findSum(int[] values, int sum) {
    Arrays.sort(values);  // O(N * log N)
    for(int i = 0; i < values.length() - 1; i ++) { // O(n)
        int remainder = sum - values[i];
        // O(log N) and assuming you can't use the same value twice.
        int pos2 = Arrays.binarySearch(value, i + 1, values.length, remainder); 
        if (pos2 >= 0)
            return new int[] { i, pos2 };
    }
    return null;
}

所以总顺序是 O(N log N) + O(N) * O(log N) 或只是 O(N log N)