LeetCode 457 环形数组是否存在循环
🟠 中等偏上
https://leetcode.cn/problems/circular-array-loop/description/
依次检查
这里检查不用双指针，一个指针即可。
class Solution {
public:
bool circularArrayLoop(vector<int>& nums) {
int n = nums.size();
for(int i = 0;i<n;i++){
int count = 0;
int cur = i;
while(true){
// 正确返回的情况
if(cur==i&&count>1) return true;
int next = (cur+nums[cur]%n+n)%n;
//只有一步环
if(next==cur) break;
//中途反向
if(nums[next]*nums[cur]<=0) break;
// -------O 走到后面有环了。
if(count>n) return true;
count++;
cur = next;
}
}
return false;
}
};
vis数组
每次到一个新的位置，设置 vis[cur] 为起点位置；每次到一个位置，查看vis[cur] 是否有值，这个值可能是本轮之前到过然后设置的（这说明又环），也可能是上一轮或之前的轮遍历时设置的，既然之前设置的并且已经开启了新的一轮，这说明这个位置不在环中，直接开启下一轮。
class Solution {
public:
bool circularArrayLoop(vector<int>& nums) {
int n = nums.size();
vector<int> vis(n,-1);
for(int i = 0;i<n;i++){
int cur = i;
if(vis[cur]!=-1) continue;
while(true){
int next = (cur+nums[cur]%n+n)%n;
if(cur==next) break;
if(nums[cur]*(nums[next])%n<0) break;
if(vis[cur]!=-1){
if(vis[cur]==i){
return true;
}else{
break;
}
}
vis[cur] = i;
cur = next;
}
}
return false;
}
};