一個整數可以由其他若幹個連續整數的和表示（java）

題目的具體描述：

一個整數N，他可能等于比它小的若幹個整數（大于2）相加。如果存在這樣的連續整數，将他們輸出，如果沒有則不輸出。

例： 整數18，18=5+6+7=3+4+5+6。是以輸出[5 6 7],[3 4 5 6]。

這是一個公司給出的筆試程式設計題，當時我沒做出來，當時一直在想總結規律，寫出效率很高的代碼，結果最後連一個可行方案都寫出來。值得反思，當時時間有限，應該先寫一個可行方案，在去考慮優化的，當時沒有編譯器進行調試，也不好測試優化的結果。

以下設：正整數為a，公差為d，項數為n。

這道題其實是一個公差為1的等差數列題，是以核心就是等差數列的公式：

a=（（首項+末項）*n）/2=首項*n+[n*(n-1)*d]/2。

可以推出：

首項=a/n-（n-1）*d/2

那麼對于一個整數a，它的等差數列最多能擁有幾項？這裡就要取極限了，對于正整數而言，1是最小的，是以假設整數N的等差數列的最大項數為max_n，其公差為d，那麼a>=1max_n+[max_n(max_n-1)*1]/2（以1為首項，d為公差的等差數列）,這個不等式就可以拿來作為邊界判斷，

而具體到本題，可以确定公差d=1，那麼公式就可以化簡：

首項=a/n-(n-1)/2

a=首項*n+[n*(n-1)]/2

邊界不等式：(max_n-1)*max_n<=2a

公式都推完了，那麼代碼也就可以出來了：

import java.util.Scanner;

public class Main {
    private static void arithmetic_squence(int num){
        // 因為不确定項數n可以為多少，是以隻能循環判斷
        // 按照題目意思，最少都是有兩項，是以i起點為2
        // i 的上限滿足：i * (i + 1) <= 2 * num 
        for (int i = 2; i * (i + 1) <= 2 * num; i++) {
            int min=(num*2/i-i+1)/2; // 等差數列的首項，也為最小項，是以命名為min
            if (min*i+(i*(i-1)/2) == num) {
                // 列印結果
                for (int j = 0; j < i; j++) {
                    System.out.print(min+j);
                    System.out.print(" ");
                }
                System.out.println();
            }
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int num = scanner.nextInt();
            long startTime = System.currentTimeMillis();//擷取目前時間
            arithmetic_squence(num);
            long endTime = System.currentTimeMillis();//擷取目前時間
            System.out.println("程式運作時間："+(endTime-startTime)+"ms");
        }
        scanner.close();
    }
}
           

其中有一個細節，首項=a/n-(n-1)/2，公式本身沒錯，但是代碼裡不能直接這麼寫，因為java的兩個int數相除是會舍棄小數位，隻保留整數位，那麼(n-1)/2，就有可能出現小數，是以為了保證沒有小數，需要先乘以2，做完差再除以2，即：

首項=[2*a/n-(n-1)]/2

這裡還得說明：假如存在一個項數為N等差數列滿足條件，那麼根據公式計算的首項一定是一個整數。反之，計算出來的首項會是一個小數。那麼java的int數計算後去掉小數點得到的首項，以此計算出來的等差數列和，會小于目标整數a，這邊是我判斷它是否滿足條件的原因。

題目中還有個細節：整數大于2，是以做邊界判斷的時候，最小整數就不是1了，而是3，是以正确的邊界判斷條件應該是：

a>=3max_n+[max_n(max_n-1)*1]/2

化簡：2a>=max_n(max_n-5)

是以弄明白了公式，随他把整數設定成多大，包括公差，也一樣可以變成其他值。

對于整數100000000（一億），有8個連續整數組合相加等于它，隻需要80ms（算上輸出到控制台的時間，和機器有關，我電腦組態很一般，約3500元的組裝機）。首先，數字越大，需要循環的次數也就越多，一億已經夠大了，80ms這個效率，應該可以接受了吧。