565. Array Nesting

A zero-indexed array A of length N contains all integers from 0 to N-1. 
Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], … } 
subjected to the rule below.

Suppose the first element in S starts with the selection of element A[i] of index = i, 
the next element in S should be A[A[i]], and then A[A[A[i]]]… By that analogy, 
we stop adding right before a duplicate element occurs in S.

Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

题目的思路很简单，循环数组，对数组的每一项进行dfs，找到最大值。
一开始我用递归写的，最后一个测试用例总是超时，后来换成了迭代，还是超时。搜了一下别人的答案，发现我的算法里面用了一个数组来存储每次dfs的结果，判断结束的条件是现在进行dfs的数字是否已经在这个数组里面。这样做会进行很多次重复的迭代，时间复杂度是 O(n^2)
改成用一个数组来存储是否进行过dfs的状态标记，这样就不会重复进行dfs，时间复杂度是 O(n)

var arrayNesting = function(nums) {
        var result = []
        var max = 0
        var inputlen = nums.length
        var nest = function (a,len,s) {
            //递归会超时
            // var temp = nums[a]
            // if(s.indexOf(temp)!=-1){
            //     return len
            // }
            // s.push(temp)
            // return nest(temp,len+1,s)
 
            //迭代更快
            while (!s[a]){
                s[a] = 1
                // s.push(a)
                a = nums[a]
                len++
            }
            return len
        }
 
        for(var i=0;i<inputlen;i++){
            var flag = new Array(inputlen)
            flag.fill(0)
            result[i] = nest(nums[i],0,flag)
            max = result[i]>max ? result[i] : max
        }
        return max
    };

以后写算法的时候，要多注意一下时间复杂度和空间复杂度，尽可能地进行优化。