[LeetCode]565. Array Nesting

https://leetcode.com/problems/array-nesting/#/description

給一個長度N的數組，裡面元素為1 ~ N - 1

找到最長的子數組

S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }.

傳回長度

從多個起點到達同一個值之後的路徑都是完全相同的，是以每個值最多周遊一次，時間複雜度O(N)，每次周遊到就加到set中

public class Solution {
    HashSet<Integer> set = new HashSet();
    public int arrayNesting(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, check(nums, i));
        }
        return max;
    }
    private int check(int[] nums, int k) {
        int res = 0;
        while (!set.contains(k)) {
            set.add(k);
            k = nums[k];
            res++;
        }
        return res;
    }
}