c# - 为什么这个代码是冰川的？

Question

我原以为这段代码可以快速执行，但对于一个包含 5000 个元素的列表，它运行了超过 20 分钟才终止它。

是因为list.contains()吗？

有什么想法吗？

     public static int PNum(int N)
     {
        List<int> result = new List<int>();
        for (int i = 1; i <= N; i++)
            result.Add(i * (3 * i - 1) / 2);

        int len = result.Count;
        int minDiff = 10000;
        int sum = 0, diff = 0;
        for (int i = 0; i <= len - 1; i++)
        {
            for (int j = i + 1; j <= len - 1; j++)
            {
                diff = result[j] - result[i];
                if (result.Contains(diff))
                {
                    sum = result[i] + result[j];
                    if (result.Contains(sum))
                    {
                        if (diff < minDiff)
                            diff = minDiff;
                    }
                }
            }
        }
        return minDiff;
    }

Answer 1

N是 5000。因此，您的外循环运行 5000 次迭代，内循环运行 5000 次迭代，List<T>.Contains遍历每个元素，因此它也进行了 5000 次迭代工作。

因此，您的循环至少要执行大约 5000³ = 125,000,000,000 次操作，这将花费相当长的时间。

问题确实是您对 List.Contains 的使用.使用 HashSet相反(或另外)得到 O(1) Contains测试。