#8787. 相反数

相反数

Background

问题描述

有 N 个非零且各不相同的整数。请你编一个程序求出它们中有多少对相反数(a 和 -a 为一对相反数)。 输入格式   第一行包含一个正整数 N。(1 ≤ N ≤ 500)。   第二行为 N 个用单个空格隔开的非零整数,每个数的绝对值不超过1000,保证这些整数各不相同。 输出格式   只输出一个整数,即这 N 个数中包含多少对相反数。

样例输入

5 1 2 3 -1 -2

样例输出

2

问题分析:

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

解法一:标记数组

由于输入的数据各不相同,并且输入数据绝对值不超过1000,这样就可以用一个下标1-1000的数组flag[]作为标记数组,用绝对值做标记就可以了,这样可以缩短数组的长度,因为实际数据的范围是-1000-1000,可以考虑把数组下标做个平移,映射为0-2000。只有数据值的范围比较小时,才可以用数组来进行标记,否则数组过长存储溢出。 需要强调的一点是,程序员应该显式地第变量进行初始化,而不是依赖于缺省的初始化。这是一个编程原则问题。

解法二:排序

对输入数据进行排序,然后再进行匹配,也是一种解决办法。这种办法有点杀鸡用牛刀的感觉,但是可以借这个解法学习一下STL的算法函数sort()的应用。另外一点,匹配是一种最为基础的编程技巧,应该掌握。 这种解法也可以不用考虑数据值的范围。 解法三:暴力搜索 暴力法也称为枚举法,被公认是一种速度慢的做法,其时间复杂度为O(n2)。然而,如果找不到好方法,有时候枚举法就是最好的方法。说是暴力搜索,还是要尽量避免重复计算,能少算一点算一点。计算量减半全靠循环控制了,一种基本的编程技巧。 解法四:用映射map做标记 用STL的map来做标记,也是一种好的做法,只需要把相反数之一用来构建map就可以了。这种解法可以不用考虑数据值的范围,只是程序计算时间和空间上代价会略为大一些。可以借这个解法学习一下map的应用。 也可以用STL的set来解决这个问题,只需要把相反数之一放入集合中就可以了,与map类似。 用Python语言程序解题 用Python语言主要用于解决应用问题,可以不必太考虑程序效率,只要程序逻辑清晰即可。这里给出的是一种字符串暴力搜索的解法,不是一种好的方案。网友给出了一种整数暴力搜索的解题方案,要好许多。 用Python语言程序来解这个题,从道理上来说,上述四种解法都可以有。 用Java语言程序解题 用Java语言程序来解这个题,从道理上来说,上述四种解法都可以有。给出一种题解程序。 程序说明:(略)

Limitation

1s, 1024KiB for each test case.