学步园

问题：快速找出一个数组中的两个数，让这两个数字之和定于一个给定的值

解法一：用两层循环，时间复杂度为O(N*N)，不可取。代码如下：

  #include<stdio.h>
  #include<iostream.h>
  
  int a[100];
  
  int main()
  {
      int n,sum;
      cout << "给定和值：";
     cin >> sum;
     
     cout << "数组中个数：";
     cin >> n;
     for(int b=0;b<n;++b)
         cin >> a[b];
     for(int i=0;i<n;++i)
     {
         for(int j=i+1;j<n;++j)
              if(a[i]+a[j]==sum) 
                 cout << a[i] << "+" << a[j] << "=" << sum << endl;
     }
     return 0;
  }

解法二：先用快速排序，然后从两端向中间找，时间复杂度为O(Nlog2N)。代码如下：

 int Partion(int* arr, int p, int r)
 {
      int temp;
      int i = p;
      int j = r;
      temp = arr[i];
      do 
      {
          while(arr[j] >= temp && i < j)
         {
             j--;
         }
         if (i < j)
         {
             arr[i++] = arr[j];
         }
         while(arr[i] < temp && i < j)
         {
             i++;
         }
         if (i < j)
         {
             arr[j--] = arr[i];
         }
     } while (i != j);
     arr[i] = temp;
     return i;
 }
 void QuitSort(int*arr, int beg, int end)//快排函数
 {
     if (beg < end)
     {
         int pn = Partion(arr, beg, end);
         QuitSort(arr, beg, pn - 1);
         QuitSort(arr, pn + 1, end);
     }
 }
 void FindTwoData(int* arr, int size, int num)
 {
     QuitSort(arr, 0, size - 1);//先用快速排序
     for (int i = 0, j = size - 1; i < j;)
     {
         if (arr[i] + arr[j] == num)
         {
             cout<<arr[i]<<"+"<<arr[j]<<"="<<num<<endl;
             i++;//这里假设(2,8)，2要求的结果是10，每个数只能用一次，不能重复使用,(2,8)用了，就不能再用(8,2)
             j--;
         }
         else if (arr[i] + arr[j] < num)
         {
             i++;
         }
         else
         {
             j--;
         }
     }
 }

解法三：用hash表，时间复杂度为O(N)也是最快的方法，但是牺牲了空间
代码如下：

void FindTwoData_Hash(int* arr, int size, int num)
{
      int *HashArry = new int[num];//申请的空间为满足条件的两个数的和的大小，实在设计不出大小为size的哈希函数
      memset(HashArry, 0, sizeof(int)*num);
      for (int i = 0; i < size; i++)
      {
          if (arr[i] <= num)//这里只考虑比num小的数
          {
              if (arr[i] + HashArry[num - arr[i]] == num)
             {
                 cout<<arr[i]<<"+"<<HashArry[num - arr[i]]<<"="<<num<<endl;
                 HashArry[arr[i]] = arr[i];
             }
             else
             {
                 HashArry[arr[i]] = arr[i];
             }
         } 
     }
     delete[] HashArry;
}