题目描述
思路解析动画文字版
记住这套「沿下标跳成环、环长即答案、走过就标记跳过」,下面每一帧都在套它。
从全新起点 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 · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题