本文共 2521 字，大约阅读时间需要 8 分钟。

1. 题目

给定一个含有正整数和负整数的环形数组 nums。

确定 nums 中是否存在循环（或周期）。

示例 1：输入：[2,-1,1,2,2]输出：true解释：存在循环，按索引 0 -> 2 -> 3 -> 0 。循环长度为 3 。示例 2：输入：[-1,2]输出：false解释：按索引 1 -> 1 -> 1 ... 的运动无法构成循环，因为循环的长度为 1 。根据定义，循环的长度必须大于 1 。示例 3:输入：[-2,1,-1,-2,-2]输出：false解释：按索引 1 -> 2 -> 1 -> ... 的运动无法构成循环，因为按索引 1 -> 2 的运动是向前的运动，而按索引 2 -> 1 的运动是向后的运动。一个循环中的所有运动都必须沿着同一方向进行。 提示：-1000 ≤ nums[i] ≤ 1000nums[i] ≠ 00 ≤ nums.length ≤ 5000 进阶：你能写出时间时间复杂度为 O(n) 和额外空间复杂度为 O(1) 的算法吗？

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/circular-array-loop

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 参考题解区

2.1 暴力解题

class Solution {
   public:    bool circularArrayLoop(vector
   
    & nums) {
           if(nums.empty()) return false;        int i, j, count, nextidx, n = nums.size();        for (i = 0; i < n; i++)        {
           	j = i;//i 是起点            count = 1;//个数计数            vector
    
      visited(n,false);//是否访问过            while(true)            {
                   if(visited[j])//重复访问，有环                    break;                visited[j] = true;                nextidx = (nums[j]%n+j+n)%n;//下一个位置                if(nums[j]*nums[nextidx] < 0)                    break;//方向反了，不对，只能朝一个方向                if(nextidx == i && count > 1)                    return true;                j = nextidx;                count++;            }        }        return false;    }};
    
   

116 ms 8.3 MB

2.2 快慢指针

class Solution {
   	int next(vector
   
    & nums, int i)	{
   		return (nums[i]%n+i+n)%n;//下一个位置	}    int n;public:    bool circularArrayLoop(vector
    
     & nums) {
       	if(nums.empty()) return false;    	int i, slow, fast, nt, count;        n = nums.size();    	for(i = 0; i < n; ++i)    	{
       		if(nums[i] == 0)    			continue;    		slow = i;    		fast = next(nums, i);//下一个位置    		while(nums[slow]*nums[fast] > 0 && nums[fast]*nums[next(nums,fast)] > 0)    		{
   	//快和慢的下一个都是同号的    			if(fast == slow)    			{
       				if(slow == next(nums, slow))    					break;//个数为1    				else    					return true;    			}    			slow = next(nums,slow);//慢的走一步    			fast = next(nums, next(nums,fast));//快的走两步    		}    		slow = i;    		while(nums[slow]*nums[next(nums, slow)] > 0)    		{
   	//把走过的点标记成0，题目说没有数字为0    			nt = next(nums, slow);    			nums[slow] = 0;//标记访问过了    			slow = nt;    		}    	}    	return false;    }};
    
   

0 ms 7.3 MB

转载地址：https://michael.blog.csdn.net/article/details/106152551 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！