題目

輸入一個正整數，若該數能用幾個連續正整數之和表示，則輸出所有可能的正整數序列。 一個正整數有可能可以被表示為n(n>=2)個連續正整數之和，如：
　　15 = 1 + 2 + 3 + 4 + 5
　　15 = 4 + 5 + 6
　　15 = 7 + 8

解題思路

i + (i+1) + ··· + (i+k) = n ，這個等式表明了i,k,n三者之間的數學關系。
給定n值，遍歷i,k中的某一值就可以得出另外一值，從而確定i到(i+k)之間的連續序列是符合要求的。

時間復雜度

O(n)

Java實現

/**
 *  題目：
 *      輸入一個正整數，若該數能用幾個連續正整數之和表示，則輸出所有可能的正整數序列。
 *      一個正整數有可能可以被表示為n(n>=2)個連續正整數之和，如：
 *      15 = 1 + 2 + 3 + 4 + 5
 *      15 = 4 + 5 + 6
 *      15 = 7 + 8
 *
 *  n = 99
 *      49  50
 *      32  33  34
 *      14  15  16  17  18  19
 *      7   8   9   10  11  12  13  14  15
 *      4   5   6   7   8   9   10  11  12  13  14
 *
 *  解題思路：
 *      i + (i+1) + ··· + (i+k) = n   =>   (2i+k)*(k+1)=2n ，這個等式表明了i,k,n三者之間的數學關系，
 *      給定n值，遍歷i,k中的某一值就可以得出另外一值，從而確定i到(i+k)之間的連續序列是符合要求的
 *
 *  時間復雜度：O(n)
 */
public class IntegerSplitContinueInteger {
    public static void main(String[] args) {
        int n = 99;
        split(n);
    }
 
    private static void split(int n) {
        for (int k = 1; k <= n / 2; ++k) {
            if ((2 * n) % (k + 1) == 0) {
                int t = (2 * n) / (k + 1) - k;
                if (t <= 0) {
                    break;
                }
                if (t % 2 != 0) {
                    continue;
                }
                int i = t / 2;
                print(i, k);
            }
        }
    }
 
    private static void print(int i, int k) {
        for (int j = i; j <= i + k; ++j) {
            System.out.printf("%d\t", j);
        }
        System.out.println();
    }
}