565.如何实现数组嵌套结构？

本文共计255个文字，预计阅读时间需要2分钟。

pythonclass Solution: def arrayNesting(self, nums: List[int]) -> int: max_len=0 seen=set()

for i in range(len(nums)): if i not in seen: count=0 start=i while start not in seen: seen.add(start) start=nums[start] count +=1 max_len=max(max_len, count)

return max_len

leetcode.cn/problems/array-nesting/

首先想到的是直接暴力遍历,以数组中每一个元素为起点，看最远能走多远：

from typing import List class Solution: # 暴力 def arrayNesting(self, nums: List[int]) -> int: result = 0 for x in nums: next_n = x s = set() while next_n not in s: s.add(next_n) next_n = nums[next_n] if len(s) > result: result = len(s) return result

一顿操作，直接超时。

思考一下，直接遍历会有很多重复的操作。如果某个元素已经出现过了，那么就不用再看它了。

from typing import List class Solution: # 暴力 def arrayNesting(self, nums: List[int]) -> int: has_appeared = set() result = 0 for x in nums: if x in has_appeared: continue next_n = x s = set() while next_n not in s: has_appeared.add(next_n) s.add(next_n) next_n = nums[next_n] if len(s) > result: result = len(s) return result