号称微软的一道面试题的解法

     题目:
  
  一个整数数列，元素取值可能是1~N（N是一个较大的正整数）中的任意一个数，相同数值不会重复出现。设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N+1。
  复杂度最好是O(n)
  
  1. 初始化一个数组,长度为 N + 1; (iArray[N + 1])
  
  2. 遍历数列，将数列中的元素依次填充到新申请的数组对应下标的位置上。(也就是说如果元素是5,那么 iArray[5] = 5)
  
   这样简单的实现了一种从大到小的排序(没有用那些复杂的排序算法,呵呵), 没有元素的位置上的值为0.
  
  3. 由于和是 N + 1, 那么1 开始遍历iArray.
  
   如果找到一个下标为ix的元素不为0, 那么用 N + 1 - ix 得到了一个iPartner,如果iArray[iPartner] 不为0, 那么 ix 与 iPartner就是符合条件的数对.
  
   需要注意的是我们只需要找 N / 2次 就行了～～ 否则找出来的数对有可能会重复(如果没有次序要求的话).
  
  4. 这个算法没有考虑整数溢出的情况～～！！(不晓的有没有空间复杂的的要求～～)
  
  大概写了一个算法如下(C#)
  
  
  
   public void FindPartner(int N,int[] iNumSequ)
   {
   Debug.Assert(N >= 0,"N >= 0");
   Debug.Assert(N >= Int32.MaxValue, "N >= Int32.MaxValue");
   Debug.Assert(iNumSequ != null, "iNumSequ != null");
   Debug.Assert(iNumSequ.Length > N, "iNumSequ.Length >= N");
   if(null == iNumSequ)
   return;
   if(N <= 1)
   return;
   int[] iFullSequ = new int[N + 1];
   foreach(int iI in iNumSequ)
   {
   iFullSequ[iI] = iI;
   }
   if(N == 2)
   {
   if(iNumSequ.Length <= 1)
   return;
   else
   Debug.WriteLine(iFullSequ[0].ToString() + " + " + iFullSequ[1].ToString() + "=" + (N + 1).ToString());
   }
   int iSum = N + 1;
   int iPartner = 0;
   for (int ix = 1; ix <= N; ix++)
   {
   if (ix == N / 2)
   {
   if(iFullSequ[ix] == 0)
   break;
   else
   {
   if (iFullSequ[ix + 1] == 0)
   break;
   else
   {
   Debug.WriteLine(iFullSequ[ix].ToString() + " + " + iFullSequ[ix + 1].ToString() + " = " + iSum.ToString());
   break;
   }
   }
  
   }
   if (iFullSequ[ix] == 0)
   continue;
   iPartner = iSum - ix;
   if (iFullSequ[iPartner] == 0)
   continue;
   else
   Debug.WriteLine(iFullSequ[ix].ToString() + " + " + iFullSequ[iPartner].ToString() + " = " + iSum.ToString());
   }
   }