环形数组是否存在循环

457. 环形数组是否存在循环,中等难度题型,可以通过快慢指针的方式来完成,需要注意的是,产生循环的节点并不是一定从0开始。从题目中可以获取到下列规则:

  • 如果nums[i]是正数,向前 移动 nums[i]
  • 如果nums[i]是负数,向后 移动 nums[i]
  • 循环序列长度 > 1

首先我们知道遍历过的点都是固定的步数,因此将遍历的点进行标记,并在下一次遇到的时候跳过该点的遍历可以减少不必要的遍历。然后从题中可得,循环是单向的,因此当方向没有调转时,可以一直试探下去,直到快慢指针相遇。即nums[slow] * nums[fast] > 0 && nums[slow] * nums[getNextIndex(nums, fast)] > 0

当快慢指针相遇时,还需要判断快指针的下一步是否为慢指针位置,即判断循环序列长度>1。快指针在这里每一步移动2次,而慢指针每一步移动1次,如果两个指针都只移动1次,快指针永远都追不上慢指针。快指针也可以移动3次、4次、5次,但是移动的次数越大,错过慢指针的几率越大,会造成两个指针相遇的时机延后,因此快指针的移动次数在2次为最佳。

下面代码为查阅题解理解后的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public boolean circularArrayLoop(int[] nums) {
int n = nums.length;
int index = 0;
for(int i = 0; i < n; i++) {
// 跳过遍历过的节点
if(nums[i] == 0) {
continue;
}
// 从第i节点出发,找出是否存在环形
int slow = i, fast = getNextIndex(nums, i);

// 说明方向相同,并且不存在已证明无回环点
while(nums[slow] * nums[fast] > 0 && nums[slow] * nums[getNextIndex(nums, fast)] > 0) {
// 当两者相等,说明指针相遇
if(slow == fast) {
// 如果快指针下一个位置为慢指针位置,说明循环长度为1,不满足要求
if(slow != getNextIndex(nums, fast)) {
return true;
} else {
break;
}
}
// 让快慢指针向后移动
slow = getNextIndex(nums, slow);
fast = getNextIndex(nums, getNextIndex(nums, fast));
}

// 本次遍历没找到回环,因此,将本次遍历过的节点都标记为0,只要从这个节点开始都不可能出现环
int add = i;
while(nums[add] * nums[getNextIndex(nums, add)] > 0) {
int temp = add;
add = getNextIndex(nums, add);
nums[temp] = 0;
}
}
return false;
}

public int getNextIndex(int[] nums, int index) {
return ((index + nums[index]) % nums.length + nums.length) % nums.length;
}
}