求解 a^3 + b^4 = c^3 + d^3 最佳运行时间

注意：这个问题不同于写出 a^3 + b^3 = c^3 + d^3 的所有解 https://stackoverflow.com/questions/14454133/write-all-solutions-for-a3-b3-c3-d3因为我需要帮助理解算法的运行时间，而不是算法是什么。

在《破解编码访谈》中，第 6 版，第 13 页。 69、有如下例子：

打印方程 a^3 + b^3 = c^3 + d^3 的所有正整数解，其中 a、b、c、d 是 0 到 1000 之间的整数。

这是给定的最佳解决方案：

1 n = 1000
2 for c from 1 to n:
3     for d from 1 to n:
4        result = c^3 + d^3
5        append(c, d) to list at value map[result]
6 for each result, list in map:
7    for each pair1 in list:
8        for each pair2 in list:
9            print pair1, pair2

书上声称运行时间是O(n^2)。

但是，我不确定如何限制第 6-9 行的复杂性。我看到第 6-7 行循环了 n^2 个数字，但我不明白第 8 行的最后一个 for 循环如何可以是恒定时间，因为整体运行时间为 O(n^2)。

事实上，我根本无法给出第 8 行的界限，因为它取决于每个列表的长度，我只能说小于 n^2，使得整个事情 O(n^4) 。

有人可以启发我吗？

我的c#解决方案

 var hash = new Hashtable();
        for (int i = 1; i <= n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                var value = Math.Pow(i, 3) + Math.Pow(j, 3);
                if (hash.Contains(value))
                    Console.WriteLine(string.Format("{0},{1},{2}", hash[value], i, j));
                else hash.Add(value, i + "," + j);
            }
        }