找出满足条件数对的个数
有一个无序整数数组，其中每个数都不相同，且每个数的取值范围为[1,N]。 设计一个时间复杂度为O(N)的算法，找出满足下面两个条件的数对的个数:
1) 相邻两个数的和也在这在这个数组之中;
2) 这两个数本身也相邻。
答: 这个数组中的数有几个特征:(1) 每个都不相同；(2) 取值范围为[1,N], 完全满足计数排序的要求。不过这里不是要排序，但是可以用相同的思想:
用一个位数组，第i位为1表示数i在数组中, 第i位为0表示数i不在数组中。这样第一个条件的验证就很简单了，只要看一个相邻两个数的和对应位是否为1即可。
下面是C++实现:
#include <bitset>#include <vector>#include <iostream>#include <set>static const int N = 100;int FindPairsCount(const std::vector<int>& vNumbers){ std::bitset<N + 1> bitArray; for(int i = 0; i < vNumbers.size(); ++i) { bitArray.set(vNumbers[i]); } int result = 0; for(int i = 1; i < vNumbers.size(); ++i) { int nSubValue = vNumbers[i] - vNumbers[i - 1]; if((1 == nSubValue || -1 == nSubValue) && bitArray.test(vNumbers[i] + vNumbers[i - 1])) { ++result; } } return result;}int main(int argc,char** argv){ int nSize = 0; while(1) { std::cout<<"请输入数组的大小，大于2且不超过100"<<std::endl; std::cin>>nSize; if(nSize >= 3 && nSize < 100) { std::cout<<"请输入"<<nSize<<"个取值范围为[1,100]的数,重复的以及不在这个范围内的都会被过滤掉:" <<std::endl; //输入数据 std::set<int> set; int iNum; while(set.size() < nSize) { std::cin>>iNum; if(iNum >= 1 && iNum <= 100) { set.insert(iNum); } } std::cout<<std::endl<<"满足条件的数对一共有:"<<FindPairsCount(std::vector<int>(set.begin(),set.end()))<<std::endl; } } return 0;}