C＃for循环的语法和时间复杂度的差异

Question

我正在尝试找出以下for循环之间的区别。

[第一个是我在codewars.com上练习算法时编写的代码。尝试较大的测试用例时，它会超时。

第二个是最佳解决方案之一。它在功能上似乎相似（显然更为简洁），但运行速度更快，并且不会超时。谁能告诉我有什么区别？另外，第二个片段中的return语句令我感到困惑。这个语法到底是什么意思？也许这是效率更高的地方。

public static long findNb(long m)
{
    int sum = 0; 
    int x = new int();
    for (int n = 0; sum < m; n++)
    {
        sum += n*n*n;
        x = n;
        System.Console.WriteLine(x);
    }
    if (sum == m)
    {
        return x;
    }
    return -1;
}

vs

public static long findNb(long m) //seems similar but doesnt time out
{
    long total = 1, i = 2;
    for(; total < m; i++) total += i * i * i;
    return total == m ? i - 1 : -1;
}

Answer 1

这两种方法大体上是same，除了不需要的System.Console.WriteLine(x);会带来乐趣：在Console（UI！）上打印是很慢的操作。

如果您正在寻找快速解决方案（尤其是对于大的m和长循环），则只需precompute所有（77936）值：

 public class Solver {
   static Dictionary<long, long> s_Sums = new Dictionary<long, long>();

   private static void Build() {
     long total = 0;

     for (long i = 0; i <= 77936; ++i) {
       total += i * i * i;

       s_Sums.Add(total, i);
     }
   } 

   static Solver() 
     Build(); 
   }

   public static long findNb(long m) {
     return s_Sums.TryGetValue(m, out long result) 
       ? result 
       : -1;
   }
 }