给定一个整数 n，让我们打印 Recaman‘s sequence 的前 n 个元素。Recaman 数列 以 0 为第一项。对于每一个后续项，我们需要计算 前一项 – 索引（如果结果为正且不在数列中）；否则，使用 前一项 + 索引。
示例：
> 输入： n = 6
> 输出： 0, 1, 3, 6, 2, 7
> 解释： 根据 Recaman 数列的规则：
>
> – 0 (第一项)
> – 0 – 1 是负数，所以使用 0 + 1 = 1
> – 1 – 2 是负数，所以使用 1 + 2 = 3
> – 3 – 3 等于 0，且 0 已在数列中，所以使用 3 + 3 = 6
> – 6 – 4 = 2 (不在数列中，所以使用它)
> – 2 – 5 是负数，所以使用 2 + 5 = 7
>
> 输入： n = 17
> 输出： 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8
目录
- [暴力解法] 使用双重嵌套循环 – O(n^2) 时间复杂度和 O(1) 空间复杂度
- [期望解法] 使用哈希表 – O(n) 时间复杂度和 O(n) 空间复杂度
[暴力解法] 使用双重嵌套循环 – O(n^2) 时间复杂度和 O(1) 空间复杂度
> 我们的想法是遵循递推规则，生成 Recaman 数列的前 n 项。首先从 0 开始，然后迭代计算下一项：如果 前一项 – 索引 的结果是 正数且不在数列中，我们就使用该值；否则，我们将使用 前一项 + 索引。
C++
CODEBLOCK_081a4677
Java
CODEBLOCK_5d57eb5d
Python
CODEBLOCK_a410a11b
C#
CODEBLOCK_a48db163
JavaScript
CODEBLOCK_737d4edb
复杂度分析：
- 时间复杂度： O(n^2)。由于我们使用了一个嵌套循环，对于每一个索引 i，我们都会遍历 i-1 个之前的元素来检查是否存在该值。这导致了 O(n^2) 的时间复杂度。
- 空间复杂度： O(1)。如果不考虑存储结果所需的输出数组，我们只使用了常数个额外变量。
[期望解法] 使用哈希表 – O(n) 时间复杂度和 O(n) 空间复杂度
> 我们可以利用一个 哈希集合 来记录已经出现过的数字，从而优化上述方法。这样，我们在检查某个值是否已存在时，可以将时间复杂度从 O(n) 降低到 O(1)。具体的算法逻辑与暴力法相同，但通过哈希表大大减少了查找时间。
C++
CODEBLOCK_bd49c651
Java
CODEBLOCK_b81e6fd7
Python
CODEBLOCK_71a9ebed
C#
CODEBLOCK_a052658e
JavaScript
CODEBLOCK_74c98808
复杂度分析：
- 时间复杂度： O(n)。由于哈希表的插入和查询操作平均时间复杂度为 O(1)，我们生成 n 个元素的总时间复杂度降为线性 O(n)。
- 空间复杂度： O(n)。我们需要一个哈希集合来存储数列中出现的元素，最坏情况下需要存储 n 个元素。