減少時間複雜度/優化的解決方案

這裏所有的倍數的總和是我的代碼：

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秒更執行一些測試用例。任何人都可以請幫助我，以減少時間複雜性？

來源

2017-08-04 Ashish Ramtri

O（n）是最好的，你可以得到這個。 – ja08prat

這個問題有一個瑣碎的恆定時間解決方案，O（1）！ –

閱讀本文[https://math.stackexchange.com/questions/9259/find-the-sum-of-all-the-multiples-of-3-or-5-below-1000](https://math .stackexchange.com /問題/ 9259 /找到最加總所有最倍數-的-3-或-5-下面-1000）。 –

作爲算術級數的總和（它們的總和等於d + 2*d + 3*d + ...），我們可以找到總數爲d的所有倍數，它們低於N。

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）

來源

2017-08-04 20:58:00 DAle

1的所有數字至（包括）N被稱爲是N（N + 1）/ 2（無需迭代）的總和。因此，從K到KM的K的所有倍數之和是上述公式的K倍，給出KM（M + 1）/ 2。

將此與@ meowgoesthedog的findMultiples（N，3）+ findMultiples（N，5） - findMultiples（N，15）想法相結合，並且您有一個恆定時間解決方案。

來源

2017-08-04 21:00:55

-1

解決您的問題的解決方案。解決您的問題的最快方法。

import java.util.*; 
class Solution { 
    public static void main(String[] args) { 
     Scanner in = new Scanner(System.in); 
     int t = in.nextInt(); 
     while(t!=0) 
     { 
      long a=in.nextLong(); 
      long q=a-1; 
      long aa=q/3; 
      long bb=q/5; 
      long cc=q/15; 
      long aaa=((aa*(aa+1))/2)*3; 
      long bbb=((bb*(bb+1))/2)*5; 
      long ccc=((cc*(cc+1))/2)*15; 
      System.out.println(aaa+bbb-ccc); 
     t-=1;} 
    } 
}

來源

2017-08-04 21:30:43

答案背後的原因不是有用的嗎？ –

減少時間複雜度/優化的解決方案

回答

相關問題