LC 457. 环形数组是否存在循环
题目描述
这是 LeetCode 上的 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：1
2
3
4
5输入：nums = [2,-1,1,2,2]
输出：true
解释：存在循环，按下标 0 -> 2 -> 3 -> 0 。循环长度为 3 。
示例 2：1
2
3
4
5输入：nums = [-1,2]
输出：false
解释：按下标 1 -> 1 -> 1 ... 的运动无法构成循环，因为循环的长度为 1 。根据定义，循环的长度必须大于 1 。
示例 3:1
2
3
4
5
6输入：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)$ 的算法吗？
模拟
根据题意，我们可以从每个下标 $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。
Java 代码：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
26class 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++;
}
}
}
C++ 代码：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
27class Solution {
public:
int n;
vector<int> nums;
bool circularArrayLoop(vector<int>& _nums) {
nums = _nums;
n = nums.size();
for (int i = 0; i < n; i++) {
if (check(i)) return true;
}
return false;
}
bool check(int start) {
int cur = start;
bool 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++;
}
}
};
Python 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution:
def circularArrayLoop(self, nums: List[int]) -> bool:
n = len(nums)
def check(start: int) -> bool:
cur = start
flag = nums[start] > 0
k = 1
while True:
if k > n:
return False
ne = ((cur + nums[cur]) % n + n) % n
if flag and nums[ne] < 0:
return False
if not flag and nums[ne] > 0:
return False
if ne == start:
return k > 1
cur = ne
k += 1
for i in range(n):
if check(i):
return True
return False
TypeScript 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24let n: number;
let nums: number[];
function check(start: number): boolean {
let cur = start;
const flag = this.nums[start] > 0;
let k = 1;
while (true) {
if (k > this.n) return false;
let next = ((cur + this.nums[cur]) % this.n + this.n) % this.n;
if (flag && this.nums[next] < 0) return false;
if (!flag && this.nums[next] > 0) return false;
if (next === start) return k > 1;
cur = next;
k++;
}
}
function circularArrayLoop(nums: number[]): boolean {
this.nums = nums;
this.n = nums.length;
for (let i = 0; i < this.n; i++) {
if (check(i)) return true;
}
return false;
};
- 时间复杂度：$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]$ 与当前轮次编号做对比，来得知该位置是否在本轮被标记。
Java 代码：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
28class 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;
}
}
C++ 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
bool circularArrayLoop(vector<int>& nums) {
int n = nums.size();
vector<int> vis(n, 0);
for(int start = 0, idx = 1; start < n; start++, idx++) {
if(vis[start] != 0) continue;
int cur = start;
bool flag = nums[cur] > 0;
while(true) {
int next = ((cur + nums[cur]) % n + n) % n;
if(next == cur) break;
if (vis[next] != 0) {
if (vis[next] != idx) break;
else return true;
}
if (flag && nums[next] < 0) break;
if (!flag && nums[next] > 0) break;
vis[next] = idx;
cur = next;
}
}
return false;
}
};
Python 代码：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
27class Solution:
def circularArrayLoop(self, nums: list[int]) -> bool:
n = len(nums)
vis = [0] * n
idx = 1
for start in range(n):
if vis[start] != 0:
continue
cur = start
flag = nums[cur] > 0
while True:
ne = ((cur + nums[cur]) % n + n) % n
if ne == cur:
break
if vis[ne] != 0:
if vis[ne] != idx:
break
else:
return True
if flag and nums[ne] < 0:
break
if not flag and nums[ne] > 0:
break
vis[ne] = idx
cur = ne
idx += 1
return False
TypeScript 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22function circularArrayLoop(nums: number[]): boolean {
const n = nums.length;
const vis = new Array(n).fill(0);
for (let start = 0, idx = 1; start < n; start++, idx++) {
if (vis[start] !== 0) continue;
let cur = start;
const flag = nums[cur] > 0;
while (true) {
let next = ((cur + nums[cur]) % n + n) % n;
if (next === cur) break;
if (vis[next] !== 0) {
if (vis[next] != idx) break;
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。
Java 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class 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;
}
}
C++ 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
bool circularArrayLoop(vector<int>& nums) {
const int OFFSET = 100010;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (nums[i] >= OFFSET) continue;
int cur = i, tag = OFFSET + i, last = -1;
bool 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;
}
};
Python 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution:
def circularArrayLoop(self, nums: List[int]) -> bool:
OFFSET = 100010
n = len(nums)
for i in range(n):
if nums[i] >= OFFSET:
continue
cur, tag, last = i, OFFSET + i, -1
flag = nums[cur] > 0
while True:
ne = ((cur + nums[cur]) % n + n ) % n
last = nums[cur]
nums[cur] = tag
cur = ne
if cur == i:
break
if nums[cur] >= OFFSET:
break
if (flag and nums[cur] < 0) or (not flag and nums[cur] > 0):
break
if last % n != 0 and nums[cur] == tag:
return True
return False
TypeScript 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22function circularArrayLoop(nums: number[]): boolean {
const OFFSET = 100010;
const n = nums.length;
for (let i = 0; i < n; i++) {
if (nums[i] >= OFFSET) continue;
let cur = i;
const tag = OFFSET + i;
let last = -1;
const flag = nums[cur] > 0;
while (true) {
let 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) || (!flag && nums[cur] > 0)) break;
}
if (last % n !== 0 && nums[cur] === tag) return true;
}
return false;
}
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.457 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
