面试之求找两个数和为某个数、几个连续数等于某个数

　　问题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,

　　感谢您的耐心查看！