LeetCode 457题 “Circular Array Loop” 是一个中等难度的算法题。题目要求我们检测一个数组中是否存在一个循环，该循环满足以下条件：

1. 循环中的元素值必须一致（即循环中的所有元素值要么都是正数，要么都是负数）。
2. 循环的长度必须大于1。

数组的每个元素都指向数组中的一个位置，即 nums[i] 表示从位置 i 跳到位置 (i + nums[i]) % n（其中 n 是数组的长度）。

题目描述

给定一个含有正整数和负整数的数组 nums，如果数组中存在一个循环，则返回 true，否则返回 false。

示例

输入: [2,-1,1,2,2] 输出: true 解释: 有一个循环，从索引 0 -> 2 -> 3 -> 0。

输入: [-1,2] 输出: false 解释: 没有循环。

解题思路

我们可以使用快慢指针（Floyd’s Tortoise and Hare）算法来检测循环。具体步骤如下：

1. 初始化快慢指针：慢指针 slow 和快指针 fast 都从当前索引 i 开始。
2. 移动指针：
   • 慢指针每次移动一步。
   • 快指针每次移动两步。
3. 检查循环：
   • 如果快指针或慢指针指向的值与当前值符号不同，则不存在循环。
   • 如果快慢指针相遇，检查循环长度是否大于1。
4. 避免重复检查：使用一个集合或标记数组来记录已经检查过的索引。

代码实现

以下是使用Python实现的代码：

def circularArrayLoop(nums): n = len(nums)

def next_index(i):
    return (i + nums[i]) % n

for i in range(n):
    if nums[i] == 0:
        continue

    slow, fast = i, i
    while True:
        slow = next_index(slow)
        fast = next_index(next_index(fast))

        if slow == fast:
            break

        if nums[slow] * nums[i] < 0 or nums[fast] * nums[i] < 0:
            break

    if slow == fast:
        # 检查循环长度是否大于1
        loop_length = 1
        fast = next_index(slow)
        while fast != slow:
            fast = next_index(fast)
            loop_length += 1

        if loop_length > 1:
            return True

return False

print(circularArrayLoop([2, -1, 1, 2, 2])) # 输出: True print(circularArrayLoop([-1, 2])) # 输出: False

解释

1. next_index函数：计算下一个索引位置。
2. 外层循环：遍历每个元素作为起点。
3. 内层循环：使用快慢指针检测循环。
4. 循环长度检查：如果快慢指针相遇，检查循环长度是否大于1。

复杂度分析

• 时间复杂度：O(n)，每个元素最多被访问两次。
• 空间复杂度：O(1)，使用了常数额外空间。

通过上述方法，我们可以有效地检测数组中是否存在满足条件的循环。希望这个解释对你理解这道题目有所帮助！如果有更多问题，欢迎继续提问。