java - 减少时间复杂度/优化解决方案

Question

座右铭是找到N以下3或5的所有倍数的和。

这是我的代码：

public class Solution
 {
 public static void main(String[] args)
  {
    Scanner in = new Scanner(System.in);
    int t = in.nextInt();
    long n=0;
    long sum=0;

    for(int a0 = 0; a0 < t; a0++)
    {
        n = in.nextInt();
        sum=0;
         for(long i=1;i<n;i++)
        {
        if(i%3==0 || i%5==0)

            sum = sum + i;
        }
   System.out.println(sum); 
    }
 }
}

对于某些测试用例，要花费超过1秒的时间。谁能帮助我，以减少时间的复杂性？

Answer 1

我们可以找到小于d的所有数字N的倍数之和作为算术级数的总和（它们的总和等于d + 2*d + 3*d + ...）。

long multiplesSum(long N, long d) {
    long highestMultiple = (N-1) / d * d;
    long numberOfMultiples = highestMultiple / d;
    return (d + highestMultiple) * numberOfMultiples / 2;
}

那么结果将等于：

long resultSum(long N) {
    return multiplesSum(N, 3) + multiplesSum(N, 5) - multiplesSum(N, 3*5);
}

我们需要减去 multiplesSum(N, 15)，因为有些数字是 3和 5的倍数，所以我们将它们相加了两次。

复杂度：O（1）