英文原文
You are playing a game involving a circular array of non-zero integers nums. Each nums[i] denotes the number of indices forward/backward you must move if you are located at index i:
- If
nums[i]is positive, movenums[i]steps forward, and - If
nums[i]is negative, movenums[i]steps backward.
Since the array is circular, you may assume that moving forward from the last element puts you on the first element, and moving backwards from the first element puts you on the last element.
A cycle in the array consists of a sequence of indices seq of length k where:
- Following the movement rules above results in the repeating index sequence
seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ... - Every
nums[seq[j]]is either all positive or all negative. k > 1
Return true if there is a cycle in nums, or false otherwise.
Example 1:
Input: nums = [2,-1,1,2,2] Output: true Explanation: There is a cycle from index 0 -> 2 -> 3 -> 0 -> ... The cycle's length is 3.
Example 2:
Input: nums = [-1,2] Output: false Explanation: The sequence from index 1 -> 1 -> 1 -> ... is not a cycle because the sequence's length is 1. By definition the sequence's length must be strictly greater than 1 to be a cycle.
Example 3:
Input: nums = [-2,1,-1,-2,-2] Output: false Explanation: The sequence from index 1 -> 2 -> 1 -> ... is not a cycle because nums[1] is positive, but nums[2] is negative. Every nums[seq[j]] must be either all positive or all negative.
Constraints:
1 <= nums.length <= 5000-1000 <= nums[i] <= 1000nums[i] != 0
Follow up: Could you solve it in O(n) time complexity and O(1) extra space complexity?
中文题目
存在一个不含 0 的 环形 数组 nums ，每个 nums[i] 都表示位于下标 i 的角色应该向前或向后移动的下标个数：
- 如果
nums[i]是正数，向前（下标递增方向）移动|nums[i]|步 - 如果
nums[i]是负数，向后（下标递减方向）移动|nums[i]|步
因为数组是 环形 的，所以可以假设从最后一个元素向前移动一步会到达第一个元素，而第一个元素向后移动一步会到达最后一个元素。
数组中的 循环 由长度为 k 的下标序列 seq 标识：
- 遵循上述移动规则将导致一组重复下标序列
seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ... - 所有
nums[seq[j]]应当不是 全正 就是 全负 k > 1
如果 nums 中存在循环，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,-1,1,2,2] 输出：true 解释：存在循环，按下标 0 -> 2 -> 3 -> 0 。循环长度为 3 。
示例 2：
输入：nums = [-1,2] 输出：false 解释：按下标 1 -> 1 -> 1 ... 的运动无法构成循环，因为循环的长度为 1 。根据定义，循环的长度必须大于 1 。
示例 3:
输入：nums = [-2,1,-1,-2,-2] 输出：false 解释：按下标 1 -> 2 -> 1 -> ... 的运动无法构成循环，因为 nums[1] 是正数，而 nums[2] 是负数。 所有 nums[seq[j]] 应当不是全正就是全负。
提示：
1 <= nums.length <= 5000-1000 <= nums[i] <= 1000nums[i] != 0
进阶：你能设计一个时间复杂度为 O(n) 且额外空间复杂度为 O(1) 的算法吗？
通过代码
高赞题解
欢迎关注我 ❤️ 提供写「证明」&「思路」的高质量专项题解
更有「长期送实体书」活动等你来 🎉 🎉
模拟
根据题意，我们可以从每个下标 $i$ 进行出发检查，如果以某个下标 $i$ 为出发点发现了「循环」，返回 True，否则返回 False。
唯一需要注意的细节是，当我们处理到的下标为 $cur$，计算下一个跳转点 $next = cur + nums[cur]$ 时，对于越过数组的情况进行处理：
如果 $next$ 为负数：在 $next$ 的基础上增加 $n * \left \lceil next / n \right \rceil$，将其映射回正值；
如果 $next$ 为正数：将 $next$ 模数组长度 $n$，确保不会越界。
整理一下，我们可以统一写成 next = ((cur + nums[cur]) % n + n ) % n。
在 check 内部，当以下任一条件出现，则可以结束检查（令 $k$ 为记录过程中扫描过的下标数量）：
如果在检查过程中，找到了与起点相同的下标，且 $k > 1$，说明存在符合条件的「循环」，返回
True；如果检查过程中扫描的数量 $k$ 超过了数组长度 $n$，那么根据「鸽笼原理」，必然有数被重复处理了，同时条件一并不符合，因此再处理下去，也不会到达与起点相同的下标，返回
False；处理过程中发现不全是正数或者负数，返回
False。
代码：
[]class Solution { int n; int[] nums; public boolean circularArrayLoop(int[] _nums) { nums = _nums; n = nums.length; for (int i = 0; i < n; i++) { if (check(i)) return true; } return false; } boolean check(int start) { int cur = start; boolean flag = nums[start] > 0; int k = 1; while (true) { if (k > n) return false; int next = ((cur + nums[cur]) % n + n ) % n; if (flag && nums[next] < 0) return false; if (!flag && nums[next] > 0) return false; if (next == start) return k > 1; cur = next; k++; } } }
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(1)$
图的遍历标记（使用新数组标记）
这是一种补充做法，更多的作为「解法一」和「解法三」之间的过渡，建议在充分理解本解法之后，再学习解法三。
从「解法一」我们发现，我们会对很多重复的路径进行重复检查。
假如从位置 $a$ 到位置 $d$ 存在一条无环通路 $a-b-c-d$，根据「解法一」我们会在对 $a$ 进行通路是否有环的检查之后，再对 $b$ 、$c$ 和 $d$ 进行路径是否有环的检查。
事实上，由于每个点只有一个出度（某个位置能跳到的下一个位置是唯一确定的），因此我们可以使用 vis 数组记录那些下标被检查过了，从而避免相同的路径被重复检查。
同时，我们可以扩充 vis 数组的功能，使其不仅仅能用于判断某个位置是否被检查过，还能记录下某个位置是在哪一轮被检查过。具体的，我们令 $vis[i] = idx$ 代表位置 $i$ 在第 $idx$ 轮被标记。
如此一来，当我们检查某个位置 $start$ 的通路时，如果遇到一个跳点 $next$，发现 $vis[next]$ 不为 $0$（代表被被记过），可通过将 $vis[next]$ 与当前轮次编号做对比，来得知该位置是否在本轮被标记。
代码：
[]class Solution { public boolean circularArrayLoop(int[] nums) { int n = nums.length; // 使用 vis 数组对每个下标进行标记 // 如果下标为 i 的位置在第 idx 轮被标记，则有 vis[i] = idx int[] vis = new int[n]; for (int start = 0, idx = 1; start < n; start++, idx++) { if (vis[start] != 0) continue; int cur = start; boolean flag = nums[cur] > 0; while (true) { int next = ((cur + nums[cur]) % n + n) % n; if (next == cur) break; if (vis[next] != 0) { // 如果 next 点已经被标记过，并且不是在本轮被标记，那么往后的通路必然都被标记，且无环，跳出 if (vis[next] != idx) break; // 如果 next 点已被标记，并且是本来被标记，说明找到了环 else return true; } if (flag && nums[next] < 0) break; if (!flag && nums[next] > 0) break; vis[next] = idx; cur = next; } } return false; } }
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
图的遍历标记（使用原数组标记）
根据题意，我们将每个下标看做“点”，「当前点」和「当前点所能到达的下一个点」看作“边”。
从而将问题转换为经典的「图论寻环」问题，同时又因为每个点出度固定为 $1$，并且规定「循环」必然是「同向」才合法，因此如果我们在遍历过程中发现存在反向，就停止检查。
另外，为实现 $O(1)$ 的空间，我们需要在原数组上进行标记，我们设立一个足够大的数 OFFSET，对于由下标 $i$ 发起的寻环操作，我们将扫描的数标记为 OFFSET + i。如果在扫描完由 $i$ 发起的寻环后，没法发现自环，说明找到了「循环」，输出 True。
代码：
[]class Solution { int OFFSET = 100010; public boolean circularArrayLoop(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { if (nums[i] >= OFFSET) continue; int cur = i, tag = OFFSET + i, last = -1; boolean flag = nums[cur] > 0; while (true) { int next = ((cur + nums[cur]) % n + n ) % n; last = nums[cur]; nums[cur] = tag; cur = next; if (cur == i) break; if (nums[cur] >= OFFSET) break; if (flag && nums[cur] < 0) break; if (!flag && nums[cur] > 0) break; } if (last % n != 0 && nums[cur] == tag) return true; } return false; } }
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 29498 | 67742 | 43.5% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
