题目描述
思路解析
一句话答案：LeetCode 565 数组嵌套：nums 是 0 到 N−1 的排列，把值当下标一路跳必然绕成若干不相交的环，沿未访问点走一遍取最长环、整环标记跳过，时间 O(n)、空间 O(n)。
从每个起点跳，最长能连出几个数
给一个数组 nums，它正好是 0 到 N−1 这些数各出现一次的排列。挑一个起点，把它的值当下标跳过去，再拿落点的值继续跳，一路收集经过的数，直到撞上收过的就停，这一串的长度就是这个起点的成绩，要返回所有起点里最长的那串。题面 nums=[5,4,0,3,1,6,2]，从下标 0 出发能连出 { 5、6、2、0 } 四个即答案 4；换成 nums=[0,1,2]，每个数都指向自己、只连出 1 个。
每个起点都从头跑一遍，同一条链数了好几遍
拿 N 个起点各跑一次最直白：从起点沿链跳到跳不出新数，数出长度，N 个取最大。可同一条链会被反复数：链上任意一点起步绕出的都是同一圈、长度也一样，却每个起点各算一遍。最坏时一整条大链长 N，每个起点都跑近 N 步，总量滑到 O(n²)，n 一大就超时。
为什么这些链一定绕回起点、还互不重叠
给每个下标 i 画一支箭头指向 nums[i]，就得到一张图：每个点恰好射出一条箭头（出度 1）；又因为是 0 到 N−1 的排列、每个值只被用一次，每个点也恰好被一条箭头指着（入度 1）。出入各一条边，从任一点走既不分叉也不断头、只能兜回自己，整张图就是若干互不相交的环——把这个排列拆成一圈圈循环，就是轮换分解。
这带来两处省法：一条环无论从哪点起步，走满一圈长度都相同，所以每条环只需走一遍；走时顺手把经过的点在一张走过标记表 visited 里记下来，之后环上别的点当起点时见它已标记就跳过。要的是单条最长环，不是把所有环拼起来。
一条环怎么走、走完怎么接着下一条
开一个 visited 布尔数组，从下标 0 扫到 N−1。碰到没标记的点，就以它为起点沿 nums 跳：每跳一步计数加一、把落点标记上，直到回到起点、记下这圈长度；碰到已标记的点就跳过。维护当前最大值，扫完即答案。参考代码用 cur 存当前落点、m 记长度，每跳一步 cur=nums[cur]、m 加一，直到 nums[cur] 又等于起点值时收圈。
手推 nums=[5,4,0,3,1,6,2] 这一组
S 是一路经过的数的集合。从下标 0 起步，值 5 收进 S、跳到下标 5；下标 5 值 6 收进、跳到下标 6；下标 6 值 2 收进、跳到下标 2；下标 2 值 0 收进、跳回下标 0——回到起点收圈。这一圈 S={5、6、2、0}，长度 4，当前最长 4。
接着下标 1 没标记，起步值 4 跳到下标 4、值 1 跳回下标 1 收圈，得 {4、1} 长 2；下标 2 已标记跳过；下标 3 起步值 3 指向自己、自成一环 {3} 长 1；下标 4、5、6 都已标记跳过。三条环长 4、2、1，最长 4 即答案。
线性从哪来，两种极端各是几
每个下标只在它所在的环里被走一次，所有环步数加起来正好 N；哪怕起点循环跑 N 轮，真正跳跃总数还是 N，时间 O(n)。额外开一个长度 N 的 visited，空间 O(n)；若允许改写输入，把走过位置改成越界哨兵值当标记，能压到 O(1)。两个极端：nums=[0,1,2] 全是自环、答案 1；所有点串成一整条大环时，答案就是 N。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「沿下标跳成环、环长即答案、走过就标记跳过」，下面每一帧都在套它。
从全新起点 0 出发（紫色是当前脚下）。把它位置上的值 5 放进集合 S，这一环现在长度 1。
现在脚踩下标 0，它的值是 5，所以下一步跳到下标 5。看看那里是不是又一个新成员。
跳到下标 5，这是新成员，把它的值 6 也收进 S。这一环长度涨到 2，继续往下跳。
现在脚踩下标 5，它的值是 6，所以下一步跳到下标 6。看看那里是不是又一个新成员。
跳到下标 6，这是新成员，把它的值 2 也收进 S。这一环长度涨到 3，继续往下跳。
现在脚踩下标 6，它的值是 2，所以下一步跳到下标 2。看看那里是不是又一个新成员。
跳到下标 2，这是新成员，把它的值 0 也收进 S。这一环长度涨到 4，继续往下跳。
现在脚踩下标 2，它的值是 0，所以下一步跳到下标 0。注意，这正好是起点，环要闭合了。
跳回起点 0，这一圈封口了。绿格里的值连起来就是集合 S = { 5、6、2、0 }，一共 4 个。比之前都长，历史最长刷新成 4。整条环染蓝表示数过了。
从全新起点 1 出发（紫色是当前脚下）。把它位置上的值 4 放进集合 S，这一环现在长度 1。
现在脚踩下标 1，它的值是 4，所以下一步跳到下标 4。看看那里是不是又一个新成员。
跳到下标 4，这是新成员，把它的值 1 也收进 S。这一环长度涨到 2，继续往下跳。
现在脚踩下标 4，它的值是 1，所以下一步跳到下标 1。注意，这正好是起点，环要闭合了。
跳回起点 1，这一圈封口了。绿格里的值连起来就是集合 S = { 4、1 }，一共 2 个。没超过已有的 4，最长不变。整条环染蓝表示数过了。
轮到起点 2，但它已经是蓝色、早就归属某个环了。按规则直接跳过，绝不重复数，这正是 visited 省下时间的地方。
从全新起点 3 出发（紫色是当前脚下）。把它位置上的值 3 放进集合 S，这一环现在长度 1。
现在脚踩下标 3，它的值是 3，所以下一步跳到下标 3。注意，这正好是起点，环要闭合了。
跳回起点 3，这一圈封口了。绿格里的值连起来就是集合 S = { 3 }，一共 1 个。没超过已有的 4，最长不变。整条环染蓝表示数过了。
轮到起点 4，但它已经是蓝色、早就归属某个环了。按规则直接跳过，绝不重复数，这正是 visited 省下时间的地方。
轮到起点 5，但它已经是蓝色、早就归属某个环了。按规则直接跳过，绝不重复数，这正是 visited 省下时间的地方。
轮到起点 6，但它已经是蓝色、早就归属某个环了。按规则直接跳过，绝不重复数，这正是 visited 省下时间的地方。
全部起点走完。最长的一圈是绿色这 4 个下标，集合 S = { 5、6、2、0 }，大小 4，就是答案。灰掉的是更短的环：{1,4} 长 2、{3} 自环长 1。
边界先想清:全自环答案是 1，一整条大环答案就是 n。
两个高频追问:O(1) 空间的哨兵技巧，以及背后的置换轮换视角。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def arrayNesting(self, nums: List[int]) -> int: n = len(nums) vis = [False] * n res = 0 for i in range(n): if vis[i]: continue cur, m = nums[i], 1 vis[cur] = True while nums[cur] != nums[i]: cur = nums[cur] m += 1 vis[cur] = True res = max(res, m) return res复杂度
- 时间：O(n)，每个下标恰好属于一个环、只被走一次，所有环加起来正好 n 步
- 空间：O(n)，visited 标记数组;若允许改写输入、用哨兵覆盖走过的位置，可降到 O(1)
易错点
面试追问把动画讲成自己的话
追问能不能把空间从 O(n) 降到 O(1)？
追问从图论角度，这道题在求什么？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最短无序连续子数组
LeetCode 581 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题