面試之求找兩個數(shù)和為某個數(shù)、幾個連續(xù)數(shù)等于某個數(shù)

2019-11-15 00:59:01

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

　　問題1、輸入一個遞增排序數(shù)組和一個數(shù)字s，在數(shù)組中查找兩個數(shù)，使得它們的和正好是s，如果有多對數(shù)字的和等于s，輸出任意一對即可。

　　顯然，很快能想到的是使用蠻力法（O（n2）），先固定一個數(shù)字，再判斷剩下的n-1個數(shù)字與它的和是否等于s。這種效率顯然有點低，我們可以使用下面比較快的方式，時間復(fù)雜度O（n）。

　　思路：我們通過兩個記錄數(shù)組的開始位置和結(jié)束位置，從數(shù)組的尾部開始，求兩個數(shù)字的和，

　　　　如果兩個數(shù)的和大于我們需要求的數(shù)s，則后面的記錄前移一位（因為是排好序的，前移一位，相當(dāng)于數(shù)值減少），再進行判斷，

　　　　如果兩個數(shù)的和小于我們要求的數(shù)s，則前面的位置記錄后移一位（因為是排好序的，后移一位，相當(dāng)于數(shù)值增加），再進行判斷，

　　　　直至找到或者后面或前面的位置記錄重合。

代碼實現(xiàn)：

/**     * 輸入一個遞增排序數(shù)組和一個數(shù)字s，在數(shù)組中查找兩個數(shù)，使得它們的和正好是s，如果有多對數(shù)字的和等于s，輸出任意一對即可。因為java只能     * 有一個返回值，這里返回了真假，或者可以改成數(shù)組，返回查找到的兩個數(shù)，這里就實現(xiàn)返回是否找到，如果找到就打印出來！     * @param data 待查找的遞增數(shù)組     * @param length 數(shù)組長度     * @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 ;  //較大數(shù)字的下標(biāo)        int behind = 0;  //較小數(shù)字的下標(biāo)                while(ahead > behind)        {            long curSum = data[ahead] + data[behind];                        if(curSum == sum)            {                System.out.
測試：
public static void main(String[] args)    {        int[] arr = {1,2,4,7,11,15};                FindSumEqualNum.FindNumberWithSum(arr,arr.length,15);    }
結(jié)果：
查找成功！兩個數(shù)為:11,4
問題2、輸入一個正數(shù)s，打印出所有和為s的連續(xù)正數(shù)序列（至少包含兩個數(shù)）。例如輸入15，由于1+2+3+4+5=4+5+6=7+8=15，所以打印出3個連續(xù)序列1~5、4~6、7~8
　　同樣，使用蠻力法也可以解決該問題，即，從1開始，不斷往后累加，直到求的值等于或者小于累加值，相等代表找到，所求值 < 累加值 ，則證明沒找到， 累加初值加一，繼續(xù)計算。可見，這樣子會重復(fù)計算很多次中間的加法，我們可以通過下面的方式，較快速得出結(jié)果，盡量減少重復(fù)的累加。
　　思路：使用兩個數(shù)small和big分別表示序列的最小值和最大值。首先把small初始化為1，big初始化為2，
　　　　　如果從small到big的序列的和大于s，我們可以從序列中減去較小的值，也就是增加small的值。
　　　　　如果從small到big的序列的和小于s，我們可以增大big讓這個序列包含更多的數(shù)字。
　　　　　因為序列至少有兩個數(shù)字，我們一直增加small到（1+s）/2為止。
代碼實現(xiàn)：
輸出查找到的連續(xù)數(shù)
/**     * 輸出從數(shù)small到big之間的所有數(shù)     * @param small 開始數(shù)【包含】     * @param big  結(jié)束數(shù)【包含】     */    public static void PrintContinuousSequence(int small,int big)    {        for(int i = small ; i <= big ; i++)        {            System.out.print(i + ",");        }        System.out.println("");    }
核心函數(shù)
    /**     * 輸入一個正數(shù)s，打印出所有和為s的連續(xù)正數(shù)序列（至少包含兩個數(shù)）     * @param sum 要求的連續(xù)的序列的和     */    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);    }
結(jié)果：
1,2,3,4,5,4,5,6,7,8,
　　感謝您的耐心查看！