试题 算法训练 相邻数对
问题描述
给定n个不同的整数，问这些数中有多少对整数，它们的值正好相差1。
输入格式
输入的第一行包含一个整数n，表示给定整数的个数。
第二行包含所给定的n个整数。
输出格式
输出一个整数，表示值正好相差1的数对的个数。
样例输入
6
10 2 6 3 7 8
样例输出
3
样例说明
值正好相差1的数对包括(2, 3), (6, 7), (7, 8)。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner
在本题目中，我们面临的是一个典型的算法问题，即寻找数组中值相差1的相邻数对。这是一个基础的数组处理和计数问题，适合初学者练习。题目来源于蓝桥杯算法训练，它要求参赛者使用编程语言（此处是Java）解决特定的数学问题。
我们来分析题目要求：
1. 输入：程序会接收两个输入，首先是整数n，表示数组的长度；然后是n个不同的整数，这些整数构成了我们的数列。
2. 输出：程序需要输出一个整数，这个整数表示数组中存在多少对值相差1的数对。
给出的Java代码实现了一个简单的暴力方法，通过双重循环遍历数组，比较每一对相邻元素是否满足条件。具体步骤如下：
- 创建一个名为`Main`的公共类，并定义`main`方法作为程序的入口。
- 使用`Scanner`类从标准输入读取数据。`Scanner sc = new Scanner(System.in);`创建了用于读取用户输入的实例。
- 读取数组的长度n，`int n = sc.nextInt();`
- 创建一个大小为n的整数数组`a`，并遍历输入读取每个整数，存储到数组中，`for (int i = 0; i < a.length; i++) { a[i] = sc.nextInt(); }`
- 关闭`Scanner`对象，释放资源，`sc.close();`
- 接下来，使用两层嵌套循环遍历数组，外层循环遍历每个元素，内层循环从当前元素的下一个元素开始，`for(int i = 0; i < a.length; i++) { for (int j = i + 1; j < a.length; j++) { ... }}`
- 在内层循环中，检查当前元素`a[i]`与相邻元素`a[j]`是否满足差值为1的条件，如果是，则将计数器`s`加1，`if ((a[i] == a[j] - 1) || (a[i] == a[j] + 1)) { s = s + 1; }`
- 输出计数器`s`的结果，`System.out.print(s);`
这个算法的时间复杂度是O(n^2)，因为我们需要遍历每个元素并与所有其他元素进行比较。对于较小的数据规模，这种解决方案是可行的。但在面对大数据时，效率较低，可以考虑优化，如使用哈希表或排序后的双指针方法，将时间复杂度降低到O(n log n)或O(n)。
总结来说，这个Java程序展示了如何使用基本的循环结构和条件判断解决算法问题。对于初学者，这是理解数组操作和计数技巧的良好实践。通过优化算法，我们可以进一步提高程序的性能，使其适应更大规模的数据处理。
