发布时间：2023-08-30 19:00
最近在上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我觉得这个没什么好说的，就是考虑所有可能性，有一个符合条件直接打破然后输出结果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");
}
}
}