int n, k;
int count = 0, diff;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input;
input = br.readLine().split(" ");
n = Integer.parseInt(input[0]);
int[] a = new int[n];
k = Integer.parseInt(input[1]);
input = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(input[i]);
for (int j = 0; j < i; j++) {
diff = a[j] - a[i];
if (diff == k || -diff == k) {
count++;
}
}
}
System.out.print(count);
这是一个示例程序，我在其中打印特定的差异计数，其中 n 范围 <=100000
现在的问题是减少这个程序的执行。我怎样才能更好地减少运行时间。
提前感谢您的建议
从文件中读取数字并将它们放入 Map 中(数字作为键，它们的频率作为值)。迭代它们一次，并为每个数字检查 map 是否包含添加了 k 的那个数字。如果是这样，请增加您的计数器。如果您使用 HashMap，那么它是 O(n)，而不是您的算法的 O(n^2)。
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int k = Integer.parseInt(br.readLine().split(" ")[1]);
Map<Integer, Integer> readNumbers = new HashMap<Integer, Integer>();
for (String aNumber : br.readLine().split(" ")) {
Integer num = Integer.parseInt(aNumber);
Integer freq = readNumbers.get(num);
readNumbers.put(num, freq == null ? 1 : freq + 1);
}
int count = 0;
for (Integer aNumber : readNumbers.keySet()) {
int freq = readNumbers.get(aNumber);
if (k == 0) {
count += freq * (freq - 1) / 2;
} else if (readNumbers.containsKey(aNumber + k)) {
count += freq * readNumbers.get(aNumber + k);
}
}
System.out.print(count);
EDIT 修复了重复项和 k = 0