https://leetcode.cn/problems/array-nesting/ 首先想到的是直接暴力遍历,以数组中每一个元素为起点，看最远能走多远： from typing import Listclass Solution: # 暴力 def arrayNesting(self, nums: List[int]) - int:
https://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