1.4.38 3-sum的初级算法的实现。通过实验评估以下ThreeSum内循环的实现性能：

for(int i=0;i<N;i++)

  for(int j=0;j<N;j++)

    for(int k=0;k<N;k++)

       if(i<j && j<k)

          if(a[i]+a[j]+a[k]==0)

             cnt++;

为此实现另一个版本的DoublingTest,计算该程序和ThreeSum的运行时间的比例。

答：

public class E1d4d38

{

    public static int countOfThreeSum(int[] a)

    {

        int N=a.length;

        int cnt=0;

        for (int i=0;i<N;i++)

            for (int j=i+1;j<N;j++)

               for(int k=j+1;k<N;k++)

                     if(a[i]+a[j]+a[k]==0)

                        cnt++;

        return cnt;

    }//end countOfThreeSum

   

   public static int countOfBasicThreeSum(int[] a)

    {

        int N=a.length;

        int cnt=0;

        for (int i=0;i<N;i++)

            for (int j=0;j<N;j++)

               for(int k=0;k<N;k++)

                   if(i<j && j<k)

                     if(a[i]+a[j]+a[k]==0)

                        cnt++;

        return cnt;

    }//end countOfBasicThreeSum

  

 

    public static void timeTrial(int N)

    {

        int MAX=1000000;

        int[] a=new int[N];

        for(int i=0;i<N;i++)

            a[i]=StdRandom.uniform(-MAX,MAX);

      

        //

        Stopwatch timerBasicThreeSum=new Stopwatch();

        int cntBasicThreeSum=countOfBasicThreeSum(a);

        double timeBasicThreeSum= timerBasicThreeSum.elapsedTime();

         //

        Stopwatch timerThreeSum=new Stopwatch();

        int cntThreeSum=countOfThreeSum(a);

        double timeThreeSum= timerThreeSum.elapsedTime();

        //

        StdOut.printf("N=%7d BasicTime=%7.1f  ThreeSumTime=%7.1f  Rate=%7.1f \n",N,timeBasicThreeSum,timeThreeSum,timeBasicThreeSum/timeThreeSum);

    }

   

    public static void main(String[] args)

    {

        for (int N=250;N<Integer.MAX_VALUE/2;N+=N)

             {

                 timeTrial(N);

             }

    }//end main

}