Leetcode565. 数组嵌套

索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], … }且遵守以下的规则。

假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]… 以此类推，不断添加直到S出现重复的元素。

输入: A = [5,4,0,3,1,6,2]
输出: 4
解释: 
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
其中一种最长的 S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

class Solution {
    public int arrayNesting(int[] nums) {
        int size = 1;
        for(int i = 0; i< nums.length ; i++){
               int count = 1;
               int next = nums[i];
            while(nums[i]!=nums[next]){
               count ++;
               next = nums[next];
            }
           size = count>size?count:size;
        }
    return size;
    }
}

大佬题解：
My initial idea is mark visited number for each start and clear out the mark before loop next start point, got TLE obviously..
The trick part here is that the numbers are always form a ring, and no matter which number of this ring you start with total count will always be same, so no need to step on it one more time……

那么将遍历后的数组元素置为-1就好了。。。

class Solution {
    public int arrayNesting(int[] nums) {
        int size = 1;
        for(int i = 0; i< nums.length ; i++){
               int count = 0;
               int next = i;
            while(nums[next]>=0){
                int newIndex = nums[next];
                nums[next] = -1;
               count ++;
               next = newIndex;     
            }
           size = count>size?count:size;
        }
    return size;
    }
}