| java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846 |
|---|
| 解题思路 |
|---|
- 将数组抽象成链表，效果如下图所示
- 题目的要求，就可以理解为，寻找最长的链表，返回其长度。
- 我们只需要长度，所以用count遍历，来记录每个链表的长度。我们只需要从起点开始走，每走一步，count+1，最终回到起点后，就得到了链表的长度。
但是，如何知道我们回到起点了呢？我们可以想象一下，我们每走一步，就在这个结点上插上一个旗子。这样的话只有两种结果，一种是我们再次看到旗子，就说明我们饶了一圈，回到了起点。或者当前链表不是一个循环链表，我们无法回到起点，最后完全遍历完链表。
- 完成后，我们可能还没有遍历完整个数组，但是其中的一个循环链表已经遍历完成，并且全部设置为-1.那么我们只需要再找到下一个不是-1的结点，重复第3步即可。
| 代码:时间复杂度O(n) 空间复杂度O(1) |
|---|
class Solution {
public int arrayNesting(int[] nums) {
int res = 0;
for (int i = 0;i < nums.length;i ++) {
if (nums[i] != -1) {//已经访问过的结点，设置为-1，如果当前结点是-1，那么跳过这次遍历
int start = i;//记录起点位置
int count = 0;//记录从起点开始，再次回到起点的步数
while (nums[start] != -1) {//只要不是-1，就说明还没有绕完一圈，没有回到起点
int x = nums[start];//获取下一步往哪里走
nums[start] = -1;//访问过的结点，设置为-1
start = x;//起点后移
count ++;//每走一步，步数count+1
}
if (count > res)//如果当前这个循环的步数，比已经记录在res的更高
res = count;//就保留更高的
}
}
return res;//返回结果
}
}
