难度: Medium
索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。
假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元素。
示例 1:
输入: A = [5,4,0,3,1,6,2]
输出: 4
解释:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
其中一种最长的 S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
提示：
1 <= nums.length <= 1050 <= nums[i] < nums.lengthA中不含有重复的元素。运行时间: 85 ms
内存: 23.8 MB
class Solution:
def arrayNesting(self, nums: List[int]) -> int:
max_length = 0
for i in range(len(nums)):
if nums[i] is not None:
current = i
length = 0
while nums[current] is not None:
temp = current
current = nums[current]
nums[temp] = None # Mark as visited
length += 1
max_length = max(max_length, length)
return max_length
这个题解使用了一种类似深度优先搜索的方法。对于每个未访问过的元素，我们从该元素开始，不断访问下一个元素，直到回到已访问过的元素形成一个环，统计环的长度。在访问过程中，将已访问的元素标记为None，避免重复访问。最后返回所有环中最大的长度。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def arrayNesting(self, nums: List[int]) -> int:
max_length = 0
for i in range(len(nums)):
if nums[i] is not None:
current = i
length = 0
while nums[current] is not None:
temp = current
current = nums[current]
nums[temp] = None # 将已访问的元素标记为None
length += 1
max_length = max(max_length, length) # 更新最大环长度
return max_length
在这个算法中直接在原数组`nums`内部使用`None`来标记已访问的元素，主要是为了节省额外的空间。使用额外的数组或集合来跟踪访问状态会导致空间复杂度增加，从O(1)变为O(n)，其中n是数组的长度。此外，直接修改原数组可以使算法实现更为简洁，并且直接操作原数组还可以减少一些内存的申请和访问时间，从而在一定程度上优化性能。
此算法利用了`nums[temp] = None`来标记已经访问过的元素。在追踪每个元素的时候，如果遇到`nums[current]`已经是`None`，说明当前元素之前已被访问，并且已经成为某个环的一部分。这样就可以确定当前的遍历已经形成了一个环，并且可以立即停止当前环的遍历。这个过程确保了每个元素只被访问一次，且能够准确识别出环的形成。
传统的深度优先搜索(DFS)通常用于图的遍历，它使用递归或栈来实现对图的深度探索。在传统DFS中，通常有一个显式的访问标记结构（如访问数组或集合）来防止重复访问。而在这个算法中，虽然也是深入探索直到无法继续（形成环），但是它通过修改原数组来标志访问过的元素，省去了额外的空间使用，并且算法的实现更为简洁。此外，这种方法更专注于追踪环的长度，而不是探索所有可能的路径。
算法通过从数组的每个索引开始追踪来确保不会遗漏任何一个环。对于每一个未被标记为`None`的索引，算法都会从该索引出发，尝试形成一个环，并且记录这个环的长度。如果形成的环长度超过当前记录的最大长度，则更新最大长度。由于每个元素在整个算法过程中只被访问和标记一次，我们可以保证算法会探索数组中的每个可能的环，从而找到并返回所有环中最大的长度。