最近在上Java课做练习时遇到一道，比较简单的Java题，暴力破解非常简单，但是出于对速度和性能的要求，我决定花更少的时间，用更少的内存去解决这道题。本博客提供两种解法，暴力破解和算法分析。

算法分析参考了一个大佬用C写的解法:http://zhidao.baidu.com/question/426301104，然后自己改了一下写成Java了。

原题：

一个正整数有可能可以被表示为n(n>=2)个连续正整数之和，如： 15=1+2+3+4+5  15=4+5+6  15=7+8  请编写程序，根据输入的任何一个正整数，若有符合这种要求的连续正整数序列输出has，否则输出none。 例如：输入15，则输出 has

输入16，则输出 none

以下是两种解法：

①暴力破解：

import java.util.*; public class NumberSum { public static void main(String[] args) { Scanner in = new Scanner(System.in); int source = in.nextInt(); int sum = 0; boolean flag = false; for(int i=1; i<source;i++) { sum = 0; for(int j=i; j<source; j++) { sum += j; if(source == sum) { flag = true; break; } } if(flag == true) { break; } } if(flag == true) { System.out.println("has"); }else { System.out.println("none"); } } }

我觉得这个没什么好说的，就是考虑所有可能性，有一个符合条件直接打破然后输出结果has，否则所有循环完没有符合条件的输出结果none。时间复杂度分析O(n^2)。

②算法分析：

这道题实际上就是一个等差数列求和，如果把数学忘了赶快回去复习一下吧。首先用数学方法分析一下:

首项：a1 = a;

尾项：an = a + (n-1)*d；这里d=1即 an = a + n -1；

等差数列求和：Sn = (a1+an)*n/2 = (2a+n-1)*n/2；（倒序相加法）

由等差数列求和，求得首项a = Sn/n + (1-n)/2;

因为Sn已知（程序输入），所以由项数n计算首项a；然后强转为int类型，若a为整数则其符合条件，标志赋予true，最后输出结果。这里条件n<=(source/2+1)，因为本题目条件的原因，所以一个数的连续数字和肯定小于等于它的一半加一，即n<(n/2)+（n/2）+1;然后这里就可以减少循环次数节省时间和空间。时间复杂度分析O(n)。

以下是源代码：

import java.util.*; public class NumberSum { public static void main(String[] args) { Scanner in = new Scanner(System.in); boolean flag = false; int source = in.nextInt(); for(float n=2; n<=(source/2+1); n++) { float a = source/n + (float)0.5 - n/2; if((int)a == a) { flag = true; break; } } if(flag == true) { System.out.println("has"); }else { System.out.println("none"); } } }