标题：【每日一题】457. 环形数组是否存在循环：一题三解：双指针 & 单指针 & 标记法，详细解释，通俗易懂！
标题：【每日一题】457. 环形数组是否存在循环：一题三解：双指针 & 单指针 & 标记法，详细解释，通俗易懂！
题目描述
存在一个不含 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] <= 1000
- nums[i] != 0
进阶：你能设计一个时间复杂度为 O(n) 且额外空间复杂度为 O(1) 的算法吗？
链接：https://leetcode-cn.com/problems/circular-array-loop
题目理解
这个题目描述的有点难以理解，下面做出解释：
针对示例1，[2,-1,1,2,2]：
- 从下标0往前走两步到下标2
- 从下标2往前走一步到下标3
- 从下标3往前走两步到下标0
所以，构成了一个循环，且满足题目要求的：沿途都是同向（全正或全负），且环数大于1
image-20210807123320639
针对示例2，[-1,2]：
下标1形成自循环，不满足题目要求环数大于1。
image-20210807124002343
针对示例3，[-2,1,-1,-2,-2]
下标1和下标2形成循环，但是不满足题目要求的沿途全正或全负的要求。
image-20210807124119154
以上图片来源：https://leetcode-cn.com/problems/circular-array-loop/solution/hua-tu-li-jie-ti-mu-by-6racious-i3habha-qsqv/
方法一、双指针法
通常来说，遇到这种求环的问题，我们都可以使用快慢指针来解决，当快指针与慢指针相遇了，说明就形成了环，但是，本题需要附带几个额外的条件，即环数大于1，且沿途全是正数或全是负数。
class Solution {
public boolean circularArrayLoop(int[] nums) {
// 2,-1,1,2,2
// 0, 1,2,3,4
// 0,2,3构成循环
// 双指针法：从每一个节点开始出发，看快慢指针是否能相遇，相遇的话就构成了环
for (int i = 0; i < nums.length; i++) {
int slow = i;
int fast = next(nums, i);
// 快慢指针方向是否一致
// 快指针每次走两步，所以，要判断慢指针与快指针的下一次是否方向也一致
while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[next(nums, fast)] > 0) {
if (slow == fast) {
if (slow != next(nums, slow)) {
return true;
} else {
break;
}
}
slow = next(nums, slow);
fast = next(nums, next(nums, fast));
}
}
return false;
}
private int next(int[] nums, int i) {
int n = nums.length;
// 考虑负值的情况，+n是把它转正
// 如果是正值的话，+n就超过n了，所以最后再%n一下
// 这里把正负情况考虑在一起了，当然也可以分开写
// 正值：(i + nums[i]) % n
// 负值：(i + nums[i]) % n + n
return ((i + nums[i]) % n + n) % n;
}
}
- 时间复杂度O(n)，虽然是双重循环，但是，内层循环在有限次会完成，并不会再遍历n次，所以，时间复杂度是小于O(n^2)的，略大于O(n)。
- 空间复杂度O(1)，只需要两个指针。
能过，运行结果较慢。
image-20210807121958652
方法二、双指针法 + 标记
上述方式，如果存在环，很快能结束，如果不存在环呢？
比如：[-2,1,-1,-2,-2]，从下标0出发，实际上把下标[3,1,2]也遍历过了，且它们是不满足条件的，所以，是不是可以在遍历下标0出发的时候把它们标记一下，下次从下标[3,1,2]出发的时候直接判定它们不合格即可。
image-20210807124119154
可以的，我们只要在每次遍历完，把不合格的沿途节点都标记一下就可以，简单点就是把数组对应下标位置的值改为0，代码如下：
class Solution {
public boolean circularArrayLoop(int[] nums) {
// 2,-1,1,2,2
// 0, 1,2,3,4
// 0,2,3构成循环
// 双指针法：从每一个节点开始出发，看快慢指针是否能相遇，相遇的话就构成了环
for (int i = 0; i < nums.length; i++) {
int slow = i;
int fast = next(nums, i);
// 快慢指针方向是否一致
// 快指针每次走两步，所以，要判断慢指针与快指针的下一次是否方向也一致
while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[next(nums, fast)] > 0) {
if (slow == fast) {
if (slow != next(nums, slow)) {
return true;
} else {
break;
}
}
slow = next(nums, slow);
fast = next(nums, next(nums, fast));
}
// 到这里表示从i出发无法构成环
// 方向相同的才需要标记，不要把反方向的标记了
int x = i;
while (nums[x] * nums[next(nums, x)] > 0) {
int tmp = next(nums, x);
nums[x] = 0;
x = tmp;
}
}
return false;
}
private int next(int[] nums, int i) {
int n = nums.length;
// 考虑负值的情况，+n是把它转正
// 如果是正值的话，+n就超过n了，所以最后再%n一下
// 这里把正负情况考虑在一起了，当然也可以分开写
// 正值：(i + nums[i]) % n
// 负值：(i + nums[i]) % n + n
return ((i + nums[i]) % n + n) % n;
}
}
- 时间复杂度O(n)，每个元素被遍历到常量次。
- 空间复杂度O(1)，只需要几个临时变量。
运行时间立马就上去了。
image-20210807130540399
方法三、单指针 + 标记
上面使用双指针来判断有没有环，那么，我们能不能只使用一个指针往前移，发现循环呢？
其实，也是可以的，不过稍微麻烦一些，比如[1,1,2]，我们从下标0出发，其实是在下标1和下标2进入循环。
所以，我们不能只打简单的标记，我们这里考虑对于每一个出发的下标打不同的标记，通过题目可值nums[i]<=1000，所以，我们可以选取一个比1000大的数做为下标的基数，在这个基数的基础上加上出发的下标本身作为标记即可。
下面请看代码吧，加了详细的注释：
class Solution {
public boolean circularArrayLoop(int[] nums) {
int BASE = 100000;
for (int i = 0; i < nums.length; i++) {
// 已经标记过，说明从这个数出发不会有环，直接跳过
if (nums[i] >= BASE) {
continue;
}
// 不能简单的标记为0了
// 标记中带上从哪个下标出发的，用于后面判断是不是从这个下标出发形成的环
int tag = BASE + i;
// 方向
int dir = nums[i];
// 当前指针
int curr = i;
// 上一次的值
int last = -1;
// 需要在遍历的过程中就标记，否则像[-1,-2,-3,-4,-5]这个用例就死循环了
while (true) {
// 已经打过标记了，里面可以跳出循环了
if (nums[curr] >= BASE) {
// 判断是不是从下标i出发打的标记
// last % nums.length != 0用于判断是不是自循环
if (nums[curr] == tag && last % nums.length != 0) {
return true;
} else {
break;
}
}
// 未打过标记，且方向相同
if (dir * nums[curr] > 0) {
// 记录上一次的值，用于上面判断是不是自循环
last = nums[curr];
// 下一次的指针
int next = next(nums, curr);
// 更新当前指针的值为标记
nums[curr] = tag;
// 往后移
curr = next;
} else {
// 方向不同，则跳出循环
break;
}
}
}
return false;
}
private int next(int[] nums, int i) {
int n = nums.length;
// 考虑负值的情况，+n是把它转正
// 如果是正值的话，+n就超过n了，所以最后再%n一下
// 这里把正负情况考虑在一起了，当然也可以分开写
// 正值：(i + nums[i]) % n
// 负值：(i + nums[i]) % n + n
return ((i + nums[i]) % n + n) % n;
}
public static void main(String[] args) {
System.out.println(new Solution().circularArrayLoop(new int[] {-1,1,-2}));
System.out.println(new Solution().circularArrayLoop(new int[] {1,1,2}));
System.out.println(new Solution().circularArrayLoop(new int[] {2,-1,1,2,2}));
System.out.println(new Solution().circularArrayLoop(new int[] {-1,2}));
System.out.println(new Solution().circularArrayLoop(new int[] {-2,1,-1,-2,-2}));
System.out.println(new Solution().circularArrayLoop(new int[] {-1,-2,-3,-4,-5}));
}
}
整个逻辑比较复杂，同学们可以到自己的IDEA中把main()方法的测试用例跑一遍，就比较清晰了。
- 时间复杂度：O(n)，因为有标记，所以，每个元素只需要遍历常量次。
- 空间复杂度：O(1)，只需要几个临时变量。
运行结果如下：
image-20210807143841616
方法三参考自：https://leetcode-cn.com/problems/circular-array-loop/solution/gong-shui-san-xie-yi-ti-shuang-jie-mo-ni-ag05/