你的位置:首页 > Java教程

[Java教程]面试之求找两个数和为某个数、几个连续数等于某个数


  问题1、输入一个递增排序数组和一个数字s,在数组中查找两个数,使得它们的和正好是s,如果有多对数字的和等于s,输出任意一对即可。

  显然,很快能想到的是使用蛮力法(O(n2)),先固定一个数字,再判断剩下的n-1个数字与它的和是否等于s。这种效率显然有点低,我们可以使用下面比较快的方式,时间复杂度O(n)。

  思路:我们通过两个记录数组的开始位置和结束位置,从数组的尾部开始,求两个数字的和,

    如果两个数的和大于我们需要求的数s,则后面的记录前移一位(因为是排好序的,前移一位,相当于数值减少),再进行判断,

    如果两个数的和小于我们要求的数s,则前面的位置记录后移一位(因为是排好序的,后移一位,相当于数值增加),再进行判断,

    直至找到或者后面或前面的位置记录重合。

代码实现

/**   * 输入一个递增排序数组和一个数字s,在数组中查找两个数,使得它们的和正好是s,如果有多对数字的和等于s,输出任意一对即可。因为java只能   * 有一个返回值,这里返回了真假,或者可以改成数组,返回查找到的两个数,这里就实现返回是否找到,如果找到就打印出来!   * @param data 待查找的递增数组   * @param length 数组长度   * @param sum 要查找的和   * @return 是否查找成功!   */  public static boolean FindNumberWithSum(int data[],int length,int sum)  {    boolean found = false;    if(length < 1)    {        return found;    }        int ahead = length -1 ; //较大数字的下标    int behind = 0; //较小数字的下标        while(ahead > behind)    {      long curSum = data[ahead] + data[behind];            if(curSum == sum)      {        System.out.println("查找成功!两个数为:"+data[ahead]+"," + data[behind]);        break;      }      else if(curSum > sum)      {        ahead -- ;      }      else      {        behind ++;      }    }    return found;  }

 

 

测试:

public static void main(String[] args)  {    int[] arr = {1,2,4,7,11,15};        FindSumEqualNum.FindNumberWithSum(arr,arr.length,15);  }

 

 

结果:

查找成功!两个数为:11,4

 

 


 

问题2、输入一个正数s,打印出所有和为s的连续正数序列(至少包含两个数)。例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以打印出3个连续序列1~5、4~6、7~8

  同样,使用蛮力法也可以解决该问题,即,从1开始,不断往后累加,直到求的值等于或者小于累加值,相等代表找到,所求值 < 累加值 ,则证明没找到, 累加初值加一,继续计算。可见,这样子会重复计算很多次中间的加法,我们可以通过下面的方式,较快速得出结果,尽量减少重复的累加。

  思路:使用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1,big初始化为2,

     如果从small到big的序列的和大于s,我们可以从序列中减去较小的值,也就是增加small的值。

     如果从small到big的序列的和小于s,我们可以增大big让这个序列包含更多的数字。

     因为序列至少有两个数字,我们一直增加small到(1+s)/2为止

代码实现

输出查找到的连续数

/**   * 输出从数small到big之间的所有数   * @param small 开始数【包含】   * @param big 结束数【包含】   */  public static void PrintContinuousSequence(int small,int big)  {    for(int i = small ; i <= big ; i++)    {      System.out.print(i + ",");    }    System.out.println("");  }

 

核心函数

  /**   * 输入一个正数s,打印出所有和为s的连续正数序列(至少包含两个数)   * @param sum 要求的连续的序列的和   */  public static void FindSeriousSequence(int sum)  {    if(sum < 3)    {      return ;    }    int small = 1;    int big = 2;    int middle = (1 + sum) / 2;    int curSum = small + big;        while(small < middle)    {      if(curSum == sum)      {        PrintContinuousSequence(small,big);      }      while(curSum > sum && small < middle)      {        curSum -= small;        small ++;                if(curSum == sum)        {          PrintContinuousSequence(small, big);        }      }            big ++;      curSum += big;          }  }

 

 

测试

public static void main(String[] args)  {    FindSeriousSequence(15);  }

 

 

结果:

1,2,3,4,5,4,5,6,7,8,

 

  感谢您的耐心查看!