各位题友大家好，@负雪明烛 又出现了。

题意

今天的题目意思比较难懂，不懂题目的朋友可以看一下本节的题意分析。

首先，要理解题目中的「环形数组」是什么。「环形数组」就是在逻辑上首尾相接的数组，即最后一个元素和第一个元素在逻辑上是相邻的（在物理存储上仍然是个普通的数组）。

那么环形数组中存在循环是什么意思呢？这就是说，在环形数组中，每个位置存储的元素表示当前位置应该向前/向后移动的步数。如果在环形数组中绕了一圈又回到了原地，那么说明数组中存在循环。

举个例子，在环形数组 [2, -1, 1, 2, 2] 中，存在循环：
image.png

同时，题目约定了循环的条件：

  • 所有 nums[seq[j]] 应当不是 全正 就是 全负，即只能沿着一个方向走。
  • k > 1，即要求环的大小 > 1。

题目的示例 2 和 3 说明了上述循环的条件。

示例 2 ，nums = [-1,2]，不算循环的原因是，循环中只有一个元素:

image.png

示例 3，nums = [-2,1,-1,-2,-2]，不算循环的原因是，循环中同时存在正、负数。

image.png

另外，需要提醒大家的是：循环的起点并不一定是位置 0.

解题思路

相信大家都做过「判断链表中是否有环」的题目，这两题的思路是一致的，常见的思路就是快慢指针，在链表问题中，快指针每次走 2 步，慢指针每次走 1 步。当快慢指针相遇的时候，说明存在环。

在本题中，题目规定了数组中每个位置存储的元素就是每次需要移动的步数。所以快指针、慢指针每次走的步数等于 nums[fast]、nums[slow]；在每一次的移动中，快指针需要走 2 次，而慢指针需要走 1 次。当快慢指针相遇的时候，说明有环。

起始时，让快指针先比慢指针多走一步，当两者在满足题目的两个限制条件的情况下，快满指针能够相遇，则说明有环。

这个题难点在于题目的两个限制条件：

  1. 在每次循环的过程中，必须保证所经历过的所有数字都是同号的。
    1. 那么，在快指针经历过的每个位置都要判断一下和出发点的数字是不是相同的符号。
  2. 当快慢指针相遇的时候，还要判断环的大小不是 1。
    1. 所以，找到相遇点的位置后，如果再走 1 步，判断是不是自己。

下面的动图展示了在环形数组 [2, -1, 1, 2, 2] 中，如何利用快慢指针寻找判断环形数组中是否存在环。

457. 环形数组是否存在循环.gif

在下面的代码中，我定义了一个 nextpos(index)的函数，用于判断每次移动后应该走到哪个位置。

python 代码如下：

  1. class Solution(object):
  2.     def circularArrayLoop(self, nums):
  3.         """
  4.         :type nums: List[int]
  5.         :rtype: bool
  6.         """
  7.         N, self.nums = len(nums), nums
  8.         for i in range(N):
  9.             slow = i
  10.             fast = self.nextpos(slow)
  11.             while nums[fast] * nums[i] > 0 and nums[self.nextpos(fast)] * nums[i] > 0:
  12.                 if fast == slow:
  13.                     if slow == self.nextpos(slow):
  14.                         break
  15.                     return True
  16.                 slow = self.nextpos(slow)
  17.                 fast = self.nextpos(self.nextpos(fast))
  18.         return False
  20.     def nextpos(self, index):
  21.         N = len(self.nums)
  22.         return (index + self.nums[index] + N) % N

刷题心得

判断链表、数组存在循环的方法是类似的，都可以使用快慢指针的方法。本题考察了我们思维变通的能力。

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！