连续正整数数列

题目描述

已知连续正整数数列{K}=K1,K2,K3…Ki的各个数相加之和为S，
i=N (0<S<100000, 0<N<100000), 求此数列K。

输入描述：输入包含两个参数，1）连续正整数数列和S，2）数列里数的个数N。

输出描述：如果有解输出数列K，如果无解输出-1

示例1：
输入：525 6
输出：85 86 87 88 89 90

解题思路

1. 暴力解法。两层for循环遍历。第一层for循环遍历S，第二层以上一层基础起点，
   遍历n次，累加和等于S则跳出。时间复杂度：O(sn)
2. 数学方程式思路。连续的整数和，假设开始的整数为m。

   S = m + (m+1) + (m+2) + (m+3) + (m+4) + ... + (m+n-1)，等差数列求和公式
   整理后：s = mn + (n*(0 + n-1)/2)
   再整理：m = s/n - (n-1)/2

代码

解法1：暴力解法

public static int[] test(int s, int n) {
    int[] res = new int[n];
    for (int i = 1; i <= s / 2; i++) {
        int temp = 0;
        for (int j = 0; j < n; j++) {
            temp += j + i;
            res[j] = j + i;
        }
        if (temp == s) {
            break;
        }
    }
    return res;
}

解法2：数学思想

public static int[] test2(int s, int n) {
    int m = s / n - (n - 1) / 2;
    if (m < 0) {
        return new int[0];
    }
    int[] res = new int[n];
    for (int j = 0; j < n; j++) {
        res[j] = j + m;
    }
    return res;
}

项目地址

• maozzi/algorithm项目 连续正整数数列 源码