LeetCode 565中等数组 · 哈希
数组嵌套 图解题解
这道题到底在问什么
数组 nums 是 0 到 N-1 的一个排列。对每个起点 i，构造集合 S = { nums[i], nums[nums[i]], nums[nums[nums[i]]], … }，不断按值当下标往前跳，直到出现重复就停。返回所有起点里最大的集合大小。
- 输入
- nums=[5,4,0,3,1,6,2]
- 输出
- 4 （S={5,6,2,0}，从下标 0 出发绕一圈）
- 输入
- nums=[0,1,2]
- 输出
- 1 （每个都是自环，最长只有 1）
最优解：一步一步想明白
- 3记住这套「沿下标跳成环、环长即答案、走过就标记跳过」，下面每一帧都在套它。
- 4从全新起点 0 出发（紫色是当前脚下）。把它位置上的值 5 放进集合 S，这一环现在长度 1。
- 5现在脚踩下标 0，它的值是 5，所以下一步跳到下标 5。看看那里是不是又一个新成员。
- 6跳到下标 5，这是新成员，把它的值 6 也收进 S。这一环长度涨到 2，继续往下跳。
- 7现在脚踩下标 5，它的值是 6，所以下一步跳到下标 6。看看那里是不是又一个新成员。
- 8跳到下标 6，这是新成员，把它的值 2 也收进 S。这一环长度涨到 3，继续往下跳。
- 9现在脚踩下标 6，它的值是 2，所以下一步跳到下标 2。看看那里是不是又一个新成员。
- 10跳到下标 2，这是新成员，把它的值 0 也收进 S。这一环长度涨到 4，继续往下跳。
- 11现在脚踩下标 2，它的值是 0，所以下一步跳到下标 0。注意，这正好是起点，环要闭合了。
- 12跳回起点 0，这一圈封口了。绿格里的值连起来就是集合 S = { 5、6、2、0 }，一共 4 个。比之前都长，历史最长刷新成 4。整条环染蓝表示数过了。
- 13从全新起点 1 出发（紫色是当前脚下）。把它位置上的值 4 放进集合 S，这一环现在长度 1。
- 14现在脚踩下标 1，它的值是 4，所以下一步跳到下标 4。看看那里是不是又一个新成员。
- 15跳到下标 4，这是新成员，把它的值 1 也收进 S。这一环长度涨到 2，继续往下跳。
- 16现在脚踩下标 4，它的值是 1，所以下一步跳到下标 1。注意，这正好是起点，环要闭合了。
- 17跳回起点 1，这一圈封口了。绿格里的值连起来就是集合 S = { 4、1 }，一共 2 个。没超过已有的 4，最长不变。整条环染蓝表示数过了。
- 18轮到起点 2，但它已经是蓝色、早就归属某个环了。按规则直接跳过，绝不重复数，这正是 visited 省下时间的地方。
- 19从全新起点 3 出发（紫色是当前脚下）。把它位置上的值 3 放进集合 S，这一环现在长度 1。
- 20现在脚踩下标 3，它的值是 3，所以下一步跳到下标 3。注意，这正好是起点，环要闭合了。
- 21跳回起点 3，这一圈封口了。绿格里的值连起来就是集合 S = { 3 }，一共 1 个。没超过已有的 4，最长不变。整条环染蓝表示数过了。
- 22轮到起点 4，但它已经是蓝色、早就归属某个环了。按规则直接跳过，绝不重复数，这正是 visited 省下时间的地方。
- 23轮到起点 5，但它已经是蓝色、早就归属某个环了。按规则直接跳过，绝不重复数，这正是 visited 省下时间的地方。
- 24轮到起点 6，但它已经是蓝色、早就归属某个环了。按规则直接跳过，绝不重复数，这正是 visited 省下时间的地方。
- 25全部起点走完。最长的一圈是绿色这 4 个下标，集合 S = { 5、6、2、0 }，大小 4，就是答案。灰掉的是更短的环：{1,4} 长 2、{3} 自环长 1。
⚠️ 容易写错的地方
✗ 错：每个起点都从头完整跑一遍环
✓ 对：环上任一点出发长度都相同，标记后整环跳过
不标记会让同一个环被反复数，退化成 O(n²) 甚至超时
✗ 错：以为答案是把所有环拼起来
✓ 对：要的是单个最长环的大小
集合 S 只沿一条链走，不同环之间不连通
✗ 错：担心链会有断头、跳不回起点
✓ 对：排列保证每点出入度都是 1，必然成环
0 到 N-1 的排列无重复，整张图就是若干不相交的环，不存在链尾
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class 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 resC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
int arrayNesting(vector<int>& nums) {
int n = nums.size();
vector<bool> vis(n);
int res = 0;
for (int i = 0; i < n; ++i) {
if (vis[i]) continue;
int cur = nums[i], m = 1;
vis[cur] = true;
while (nums[cur] != nums[i]) {
cur = nums[cur];
++m;
vis[cur] = true;
}
res = max(res, m);
}
return res;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int arrayNesting(int[] nums) {
int n = nums.length;
boolean[] vis = new boolean[n];
int res = 0;
for (int i = 0; i < n; i++) {
if (vis[i]) {
continue;
}
int cur = nums[i], m = 1;
vis[cur] = true;
while (nums[cur] != nums[i]) {
cur = nums[cur];
m++;
vis[cur] = true;
}
res = Math.max(res, m);
}
return res;
}
}复杂度
时间
O(n)
每个下标恰好属于一个环、只被走一次，所有环加起来正好 n 步
空间
O(n)
visited 标记数组;若允许改写输入、用哨兵覆盖走过的位置，可降到 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 数组嵌套 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能把空间从 O(n) 降到 O(1)？+
可以。不另开 visited 数组，而是直接把走过的位置在 nums 里改成一个哨兵值（比如 N，反正合法值都在 0 到 N-1）。下次遇到哨兵就知道这条环已经数过，直接跳过。代价是修改了输入数组，面试时要先和面试官确认能不能改。
从图论角度，这道题在求什么？+
一个 0 到 N-1 的排列对应一个有向图，每个点出度入度都是 1，等价于若干互不相交的环，也就是置换的轮换分解。题目要的就是最长那个环的长度。想通这层，代码只是「遍历每个环、记录最长」。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 数组嵌套 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。