Background

问题描述

给定n个不同的整数，问这些数中有多少对整数，它们的值正好相差1。 输入格式 　　输入的第一行包含一个整数n，表示给定整数的个数。 　　第二行包含所给定的n个整数。 输出格式 　　输出一个整数，表示值正好相差1的数对的个数。

样例输入

6 10 2 6 3 7 8

样例输出

3

样例说明

值正好相差1的数对包括(2, 3), (6, 7), (7, 8)。 评测用例规模与约定 　　1<=n<=1000，给定的整数为不超过10000的非负整数。

问题简述：（略）

问题分析：

重写解题博客以及解题程序代码（参见参考链接），解题逻辑更加清晰，解题代码更加简洁，多种解法顺序更加合理。

解法一：标记数组

由于输入的数据各不相同，并且输入数据为不超过10000的非负整数，这样就可以用一个下标0-10001的数组flag[]作为标记数组，数组flag[]所有元素的初值均为0，出现过a则flag[a]置值为1。每当读入一个数a，判定一下是否为相邻数并且进行计数就可以了。只有数据值的范围比较小时，才可以用数组来进行标记，否则数组过长存储溢出。 需要强调的一点是，程序员应该显式地第变量进行初始化，而不是依赖于缺省的初始化。这是一个编程原则问题。

解法二：排序

对输入数据进行排序，然后再顺序判定数是否相邻，并且进行统计计数就好了，也是一种解决办法。这种办法有点杀鸡用牛刀的感觉，但是可以借这个解法学习一下STL的算法函数sort()的应用。 这种解法也可以不用考虑数据值的范围。

解法三：暴力搜索

暴力法也称为枚举法，被公认是一种速度慢的做法，其时间复杂度为O(n2)。然而，如果找不到好方法，有时候枚举法就是最好的方法。说是暴力搜索，还是要尽量避免重复计算，能少算一点算一点。计算量减半全靠循环控制了，一种基本的编程技巧。

解法四：用集合set来实现

用STL的set来存放已经出现的数，也是一种好的做法。每当读入一个数，只需要判定一下相邻的数是否已经在集合里就可以了。这种解法可以不用考虑数据值的范围，只是程序计算时间和空间上代价会略为大一些。可以借这个解法学习一下set的应用。 也可以用STL的map来解决这个问题，类似于做标记，不 如set简单。

用Python语言程序解题

用Python语言主要用于解决应用问题，可以不必太考虑程序效率，只要程序逻辑清晰即可。可以暴力搜索，也可以排序后再处理。 用Python语言程序来解这个题，从道理上来说，上述四种解法都可以有。

用Java语言程序解题

用Java语言程序来解这个题，从道理上来说，上述四种解法都可以有。给出一种题解程序，还可以有各种各样程序写法。

Limitation

1s, 1024KiB for each test case.