数组嵌套 图解题解

从每个起点跳，最长能连出几个数

给一个数组 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。

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 res

C++

#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;
    }
}