java - 求和超时如何解决？

Question

我正在解决HackerRank(Euler项目，问题1)中的一个非常直接的问题，该问题说要找出低于特定给定数字(n)的所有数字的总和，该数字返回零作为潜水提醒减少 3 或 5 。我写的解决方案如下，

public static int getSum(int n ){

    int sum  = 0;

    for (int j =0; j < n; j++){

        if ( j%3 == 0  || j%5 == 0 ){

            sum += j;
        }      
    }
    return sum; 
}

在 2 个测试用例中，此解决方案超时。如何改进代码？

Answer 1

难道就没有其他办法可以解决吗？

如果n为10^6，则循环运行10^6次。

我们可以进一步减少这个吗？

还记得艺术进步系列吗？

a、a + n、a + 2n、...

这和问题之间有什么联系吗？

是的，看3倍数还是5倍数。

3, 3 + 3, 3 + 2 * 3....

第n项之前的总和是多少？

对 5 多重数使用相同的方法。

我不想因为给你完整的答案而破坏解决欧拉计划问题的乐趣。我给了你一个提示。玩得开心!

<小时/>

PS:这有一个转折。仔细观察。