环形数组是否存在循环

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/circular-array-loop

题目描述:

存在一个不含 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]] 应当不是全正就是全负。

题目分析:

判断数组中是否存在环形数组，那么什么是环形数组?

存在一个数组nums[a, b, c, d, e]，该数组中每个索引位置存储的元素表示当前索引应该向前还是向后移动的位数，例如数组nums索引i移动后的下个位置等于nums[i] + i(未考虑超过数组边界)。如果从某个起点移动n次之后又回到了原点，则代表该数组是环形数组。

例如：数组nums[2, 3, 1, 3, 1, -3],就是一个环形数组，从图中可以看出来，索引0->2->3->0构成了循环。

循环长度必须大于1
例如：数组nums[-1,2],虽然索引1->1也构成了循环，但是不符合要求，需要返回false.
循环中移动的方向应当不是全正就是全负
例如：数组nums[-2,1,-1,-2,-2],存在1->2->1索引且循环长度大于1，也需要返回false,因为循环同时存在了正向和反向移动.

思路一：

当前索引i,长度为len的数组nums,计算下一个位置：next = (nums[i] + i)
- 这时有两种情况：

next >= 0，则next = next % len
next < 0, 则next = (next * -1 == len) ? 0 : (next % len) + len;

通过上面的两个公式之一计算出来的新索引位置next如果等于i,说明循环长度为1
在对数组进行遍历的过程中，从索引0开始第一次访问走过无环路经：0->1->2->3->5->7.再从索引1开始时：1->2->3->5->7会被重复访问。可以通过一个数组维护已经访问的节点。并且如果在同一轮循环中重复访问到某一个节点，说明数组成环。

代码实现：

class Solution {
    public int[] arr;
    public int[] mark;
    public int len;
    public boolean circularArrayLoop(int[] nums) {
        len = nums.length;
        arr = nums;
        mark = new int[len];
        for (int i = 0; i < len; i++) {
            if (mark[i] != 0) continue;
            if (doubleArr(i)) return true;
        }
        return false;
    }
    public boolean doubleArr(int index) {
        int cur = index;
        boolean flag = arr[cur] > 0;
        boolean plusMinus = flag;
        while (true) {
            int next = arr[cur] + cur;
            if (next >= 0) {
                next = next % len;
            } else {
                next = (next * -1) == len ? 0 : (next % len) + len; 
            }
            if (next == cur) break;
            if (flag && arr[next] < 0) return false;
            if (!flag && arr[next] > 0) return false;
            
            if (mark[next] != 0) {
                if (mark[next] == index + 1) return true;
                if (mark[next] != index + 1) break;
            }
            mark[next] = index + 1;
            cur = next;
        }
        return false;
    }
}

思路一：

对于本题到数组求环，可以抽象成链表求环，然后利用快慢指针解决。
从图中可以看出来，以索引0为“头节点”展开抽象成一个链表，问题也就变成了求该链表是否存在环.

代码实现：

class Solution {
    int[] arr;
    int len;
    public boolean circularArrayLoop(int[] nums) {
        len = nums.length;
        arr = nums;
        for (int i = 0; i < len; i++) {
            if (doubleArr(i, nextIdx(i))) return true;
        }
        return false;
    }
    // slow:慢指针，fast:快指针.
    public boolean doubleArr(int slow, int fast) {
  
        while (true) {
            if (arr[fast] * arr[slow] < 0) return false;  // 是否同向
            if(arr[nextIdx(fast)] * arr[slow] < 0) return false; // 是否同向
            if (fast == slow) { // 快慢指针相遇.
                if (slow == nextIdx(slow)) return false; // 循环长度为1.
                return true; 
            }
            fast = nextIdx(nextIdx(fast));
            slow = nextIdx(slow);
        }
    }
    // 计算下一个节点坐标.
    public int nextIdx(int index) {
        int next = arr[index] + index;
        if (next >= 0) {
            next = next % len;
        } else {
            next = (next * -1) == len ? 0 : (next % len) + len; 
        }
        return next;
    }
}