### 题目

You are given an array of positive and negative integers. If a number n at an index is positive, then move forward n steps. Conversely, if it’s negative (-n), move backward n steps. Assume the first element of the array is forward next to the last element, and the last element is backward next to the first element. Determine if there is a loop in this array. A loop starts and ends at a particular index with more than 1 element along the loop. The loop must be “forward” or “backward’.

Example 1: Given the array [2, -1, 1, 2, 2], there is a loop, from index 0 -> 2 -> 3 -> 0.

Example 2: Given the array [-1, 2], there is no loop.

Note: The given array is guaranteed to contain no element “0”.

Can you do it in O(n) time complexity and O(1) space complexity?

### 一个fast一个slow指针

• fast每次跳跃两下
• slow每次跳跃一下

#### 代码

class Solution {

public boolean circularArrayLoop(int[] nums) {
if (nums == null || nums.length == 0) { return false; }
localNums = nums;
size = nums.length;
isForward = (nums[0] > 0);
int slow = 0, fast = 0;
do {
for (int i = 0; i < 2; i++) {
if (isCrossward(fast)) return false;
fast = skip(fast);
}
slow = skip(slow);
} while (slow != fast);
return fast == 0; // something they called loop here must go back to the first element
}

// environment
private int[] localNums;
private int size;
private boolean isForward;

private int skip(int index) {
index += localNums[index];
if (isForward && index >= size) {
index %= size;
} else if (!isForward && index < 0) {
index = index % size + size;
}
return index;
}

private boolean isCrossward(int index) {
return (isForward && localNums[index] < 0) || (!isForward && localNums[index] > 0);
}

}