LeetCode 565. 数组嵌套

2026-09-13 HGNULB 约 4 分钟

文章信息 2 个分类 2 个标签

分类

LeetCode 中等

题目描述

✅ 565. 数组嵌套

题意分析

数组是 0...n-1 的一个排列。从某个位置出发，不断把当前值当成下一个下标，直到即将出现重复值，求能够得到的最多不同元素数量。

将每个下标看作节点，i → nums[i] 看作后继关系。每个节点有一个后继，而排列中每个值又恰好出现一次，所以每个节点也恰好有一个前驱。

解法：全局标记并遍历每个环

核心思路

[!blue]

有限个节点沿唯一后继不断前进，最终一定重复。这里不会出现一条外部链汇入某个环：否则环入口同时有环内前驱和链上前驱，与每个节点只有一个前驱矛盾。因此整张图恰好由互不相交的环组成。

从一个环里的任意位置出发，都会经过这个环的全部节点后回到起点，所以题目要找的就是最大环长度。题目序列从 nums[i] 开始，代码从下标 i 开始计数，两者只是在同一环上换了起点，长度相同。

用一个全局 visited 数组。枚举起点时，如果它还未访问，就顺着后继走，每到一个新节点先标记，再把本轮长度加一。再次遇到已访问节点时停止，这一轮已经完整统计了所在的环。

全局标记可以跨起点保留，因为不同环不会汇合。从未访问节点出发不会接入已经处理的另一座环；同一环中的其他起点以后也无需重新计数。代码中已访问起点不会进入内层循环，长度保持 0，不影响已有最大值。

解题步骤

建立长度为 n 的访问数组，最大长度 answer 初始化为 0。

依次枚举起点，将当前位置设为 start，本轮长度设为 0。

当前位置未访问时，先标记并计数，再跳到 nums[node]。

遇到已访问位置就结束本轮，用环长度更新最大值。

所有起点处理完后返回最大值。指向自身的节点也会先被计数一次，因此自环长度为 1。

代码实现

class Solution {
    public int arrayNesting(int[] nums) {
        boolean[] visited = new boolean[nums.length];
        int answer = 0;

        for (int start = 0; start < nums.length; start++) {
            int node = start;
            int length = 0;

            while (!visited[node]) {
                visited[node] = true;
                length++;
                node = nums[node];
            }

            answer = Math.max(answer, length);
        }

        return answer;
    }
}

func arrayNesting(nums []int) int {
    visited := make([]bool, len(nums))
    answer := 0
    for start := range nums {
        node, length := start, 0
        for !visited[node] {
            visited[node] = true
            length++
            node = nums[node]
        }
        answer = max(answer, length)
    }
    return answer
}

复杂度分析

时间复杂度：$O(n)$。外层检查 n 个起点，内层每次都标记一个此前未访问的节点，所有内层循环合计最多执行 n 次。

空间复杂度：$O(n)$，来自全局访问数组；其余变量为常数空间，原数组不被修改。

关键点总结

[!green]

排列保证每个节点入度、出度均为 1，所以只有互不相交的环。

一个环只需完整统计一次，之后从环内其他位置出发得到的长度相同。

全局标记让总遍历量保持线性，关键依据是不同环不会汇合。

易错点总结

[!yellow]

每换起点就清空访问标记：会多次遍历同一个环，最坏退化为平方时间。

把自环当成长度 0：当前位置本身也是一个不同元素，必须计入一次。

把下标加一当成下一步：后继由 nums[node] 决定，与数组中相邻位置无关。

把本结论直接用于含重复值的数组：那样可能有多条链汇入同一个环，不能仅靠全局标记后的本轮步数求最长长度。

相似题目

题目	难度	关联与区别
287. 寻找重复数	中等	同样把数组值视为下一下标；原题有重复值，需要找环入口，本题的排列形成互不相交的纯环。
141. 环形链表	简单	都沿后继关系识别环；本题还要枚举全部独立环并取最大长度。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/61741407

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！