Code & Func

第12天。

总感觉这道题是刷过的。这道题的输入是一个由0到 N-1 组成的数组，按照S[i] = {A[i], A[A[i]], A[A[A[i]]], ... } 的规则，找到S[i]最长的长度。

显然按这种走法，这个数组会是由多个环组成的，也就是我们要找出最长那个环的长度，我们只需要简单的去寻找即可，而且一旦我们经过了某个元素，一定不会出现在其他人的环中了，所以我们可以将其赋值为-1表示已经使用过来。

这样，我们的算法就是O(n)的复杂度了：

1
class Solution {
2
public:
3
    int arrayNesting(vector<int>& nums) {
4

5
        int res = 0;
6
        for(int i = 0;i < nums.size(); i++) {
7
            if (nums[i] < 0) continue;
8
            res = max(res, helper(nums, i));
9
        }
10
        return res;
11
    }
12

13
    int helper(vector<int> &nums, int index) {
14
        int c = 0, j = nums[index];
15
        nums[index] = -1;
9 collapsed lines
16
        while(j >= 0) {
17
            int t = nums[j];
18
            nums[j] = -1;
19
            j = t;
20
            c++;
21
        }
22
        return c;
23
    }
24
};