由于题目是限定了数组是 环形 的，所以可以假设从最后一个元素向前移动一步会到达第一个元素，而第一个元素向后移动一步会到达最后一个元素。 因此我们需要对两种越界分开讨论。不过为了代码一致，我用了统一的写法 (cur + nums[cur]) % n + n ) % n 获取到下一个索引。
代码
语言支持：Python3
Python3 Code:
class Solution:
def circularArrayLoop(self, nums: List[int]) -> bool:
def can(cur, start, steps):
if nums[cur] ^ nums[start] < 0: return False
if cur == start and steps != 0: return steps > 1
if cur in visited: return False
visited.add(cur)
return can(((cur + nums[cur]) % n + n ) % n, start, steps + 1)
n = len(nums)
visited = None
for i in range(n):
visited = set()
if can(i, i, 0): return True
return False
复杂度分析
令 n 为数组长度。
时间复杂度：$O(n^2)$
空间复杂度：$O(n)$
解法二 - 空间优化
思路
和解法一类似。不过由于如果 steps 大于 n 则一定不存在解，可直接返回 False，因此我们可以根据 steps 判断是否无解，而不必使用 visited 数组。这样做可以减少空间，不过时间复杂度上常数项上要比解法一差，因此不推荐，仅作为参考。
代码
语言支持：Python3
Python3 Code:
class Solution:
def circularArrayLoop(self, nums: List[int]) -> bool:
def can(cur, start, steps):
if nums[cur] ^ nums[start] < 0: return False
if cur == start and steps != 0: return steps > 1
if steps > n: return False
return can(((cur + nums[cur]) % n + n ) % n, start, steps + 1)
n = len(nums)
for i in range(n):
if can(i, i, 0): return True
return False
