一個(gè)長(zhǎng)為 N 且下標(biāo)從 0 開始的數(shù)組 A 包含 從 0 到 N - 1 的所有整數(shù)。找到并返回集合 S 的最大長(zhǎng)度，其中S [i] = {A [i]停团，A [A [i]]，A [A [A [i]]]掏熬，...}受到以下規(guī)則的約束佑稠。
假設(shè) S 中的第一個(gè)元素以選擇 index = i的元素A [i]開始，S中的下一個(gè)元素應(yīng)該是A [A [i]]旗芬，然后是A [A [A [i]]] ... 通過(guò)這個(gè)類比舌胶，我們?cè)赟中出現(xiàn)重復(fù)元素之前就停止添加。
樣例1
輸入: [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.
其中一個(gè)最長(zhǎng)的S [K]：
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
樣例2
輸入: [0,1,2]
輸出: 1
題意：關(guān)鍵是弄懂 S [i] = {A [i]疮丛，A [A [i]]幔嫂，A [A [A [i]]]辆它，...}
思路1、使用遞歸會(huì)超時(shí) 使用 set 存儲(chǔ) s[i] 中的元素履恩，出現(xiàn)重復(fù)的遞歸結(jié)束
思路2锰茉、遍歷數(shù)組 使用 set 存在 s[i]中的元素，當(dāng) set 出現(xiàn)重復(fù)的時(shí)候跳過(guò)切心， 定義一個(gè)中間變量 temp white循環(huán)set 不包含 temp 實(shí)現(xiàn)如下
public class Solution {
/**
* @param nums: an array
* @return: the longest length of set S
*/
public int arrayNesting(int[] nums) {
// Write your code here
int result = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
Set<Integer> set = new HashSet<>();
helper(nums, i, set);
result = Math.max(result, set.size());
}
return result;
}
private void helper(int[] nums, int i, Set<Integer> set) {
if (set.contains(nums[i])) {
return;
}
set.add(nums[i]);
helper(nums, nums[i], set);
}
public class Solution {
/**
* @param nums: an array
* @return: the longest length of set S
*/
public int arrayNesting(int[] nums) {
int result = Integer.MIN_VALUE;
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (set.contains(i)) {
continue;
}
int count = 0;
int temp =i;
while (!set.contains(temp)) {
set.add(temp);
count++;
temp = nums[temp];
}
result = Math.max(result, count);
}
return result;
}
}
}
