我遇到了这段代码的问题.我不想看别人,所以我想知道我的错是什么.
如果我们列出10以下的所有自然数是3或5的倍数,我们得到3,5,6和9.这些倍数的总和是23.
求出1000以下3或5的所有倍数的总和.
public class Multiples {
public static void main (String [] args) {
int temp = 0;
int temp2 = 0;
for (int i = 0; i <= 1000; i++) {
if (i % 3 == 0) {
temp = temp + i;
}
}
for (int j = 0; j <= 1000; j++) {
if (j % 5 == 0) {
temp2 = temp2 + j;
}
}
System.out.println(temp + temp2);
}
}@H_403_7@
解决方法
解决方案
1)O(n)：
其他答案的一个小改进(我可以从3开始)：
public static void main(String[] args) {
int sum = 0;
for (int i = 3; i < 1000; i++) {
if (i % 3 == 0 || i % 5 == 0) {
sum += i;
}
}
System.out.println(sum);
}@H_403_7@
对于更大的输入数字(Integer.MAX_VALUE而不是1000),需要：
> 195秒
2)O(n)= O(n / 3)O(n / 5)O(n / 15)：
public static void main(String[] args) {
long sum = 0 ;
for ( long i = 3 ; i < 1000 ; i+=3 ){
sum+=i;
}
for ( long i = 5 ; i < 1000 ; i+=5 ){
sum+=i;
}
for ( long i = 15 ; i < 1000 ; i+=15 ){
sum-=i;
}
System.out.println(sum);
}@H_403_7@
在第一种情况下,对于i,我们有大约n(1000)个值,在第二种情况下,我们只有大约n / 3 n / 5 n / 15(600)的值.第二个也更好,因为比较较少(如果涉及则没有).
对于更大的输入数字(Integer.MAX_VALUE而不是1000),需要：
> 9秒
3)O(1)：
该解决方案基于以下观察：
1 + 2 + … + n = n*(n+1)/2
public static void main(String[] args) {
int nr = 1000;
nr--;
int x3 = nr/3;
int x5 = nr/5;
int x15 = nr/15;
long sum1 = 3*x3*(x3+1);
long sum2 = 5*x5*(x5+1);
long sum3 = 15*x15*(x15+1);
long sum = (sum1+sum2-sum3)/2;
System.out.println(sum);
}@H_403_7@
在这种情况下,即使输入为Integer.MAX_VALUE,计算也非常快(小于1 ms).
