前言

中等算法难度，记录这个题是为了总结自己前面刷题的不足以及解决环问题的一些经验。

问题所在
以前解决问题，总觉得只需要分析问题，转换问题就完了。其实没这么简单。能解决以前那些题，是因为那些题所需的知识，我都牢牢掌握，所以分析问题起来很简单。但是今天碰到的题，我用所掌握的方法却达不到更快的速度，所以我采用了前几天一个找环的思路解决了。
解决方案
以上的问题就在刨析问题本身，自己是否具有好的基础知识。而当我们有时，就只需要分析转换问题，然后coding，完事，这就是所谓的思。而没有时，我不应该去死咳，浪费一天时间可能也想不出来。这个时候我应该去学习官方提供的解题思路，掌握其中的解题技巧，举一反三触类旁通，这就是所谓的学。
所以我需要学思结合去面对所有的算法题，不断积累，不断进步。
注意事项
第一次看到三色法+DFS，看懂了代码，但是根本没理解透，无法应用到其他上面去，但是沉下心来，专心看，长时间的专心致志，将每一步装进脑子而不打断，就能吃透算法。
环问题
初始化status[]数组，进入递归，未被访问节点为初始化的0，被访问节点设为1，当前正在递归中的节点设为2。这样来快速记录所有状态，这也是我提高速度的关键。
之前我用status[]存节点状态，0表示未访问，1表示访问过。而正在递归中的节点怎么办？我申请了一个ArrayList（这是我所学知识想的基础想法）去存中途的节点，通过add()和removeAll(自身)去做到记录和更新节点。由于ArrayList这两个方法的原理，是很浪费CPU时间，例如add()时，JVM会重新申请一个新的ArrayList去存以前的元素和当前元素，非常浪费时间。

二、问题

1、剖析问题

按照游戏规则，nums自己的下标+自己的数=nums下一个下标。通过节点是否走过来循环，通过取余去循环向前走，走过的节点都记录一下。
判断前方是否与自己异号，若异号，则重新游走。若前方是已访问节点，则重新游走。
用list把当前走过的节点记录起来，当走到list里的节点。(初始想法)
判断此下标是不是当前下标，若是，continue;若不是，则返回true.

2、源代码

public boolean circularArrayLoop(int[] nums) {
		/*
		 * 分析问题 按照游戏规则，nums自己的下标+自己的数=nums下一个下标。 通过节点是否走过来循环，通过取余去循环向前走，走过的节点都记录一下。
		 * 判断前方是否与自己异号，若异号，则重新游走。若前方是已访问节点，则重新游走。 用list把当前走过的节点记录起来，当走到list里的节点。
		 * 判断此下标是不是当前下标，若是，continue;若不是，则返回true.
		 */
		int len = nums.length;
		int[] status = new int[len];
		for (int i = 0; i < len; i++) {
			if (status[i] == 1)
				continue;
			//c为current
			int c = i;
			if (isLoop(c, status, nums)) {
				status[c] = 1;
				return true;
			}
			status[c] = 1;
		}
		return false;
	}

	private boolean isLoop(int c, int[] status, int[] nums) {
		status[c] = 2;
		int len = status.length;
		int next = (c + (nums[c] % len) + len) % len;
		//已判断节点，自己到自己的循环，异号节点，三类按顺序"巧"归一。
		if (status[next] == 1 || c == next || nums[c] * nums[next] < 0)
			return false;
		if (status[next] == 2) {
			return true;
		}
		if (isLoop(next, status, nums)) {
			status[next] = 1;
			return true;
		} else {
			status[next] = 1;
			return false;
		}
	}

三、评估

1、时间复杂度

O(n)，n为节点长度。

2、空间复杂度

O(n)，n为节点长度

四、更新

进阶挑战
进阶：你能设计一个时间复杂度为 O(n) 且额外空间复杂度为 O(1) 的算法吗？

1、分析

由于我们不是每个节点都要进入循环，这样本身就大大加快了时间，而访问过的节点其实已经就没什么作用了，我把访问了的节点即无用的节点用气来，刚好契合三色法。这样就将空间复杂度提升到O(1)

2、源代码(用递归)

public boolean circularArrayLoop(int[] nums) {
		/*
		 * 分析问题 按照游戏规则，nums自己的下标+自己的数=nums下一个下标。 通过节点是否走过来循环，通过取余去循环向前走，走过的节点都记录一下。
		 * 判断前方是否与自己异号，若异号，则重新游走。若前方是已访问节点，则重新游走。 用list把当前走过的节点记录起来，当走到list里的节点。
		 * 判断此下标是不是当前下标，若是，continue;若不是，则返回true.
		 */
		int len = nums.length;
		//int[] status = new int[len];
		for (int i = 0; i < len; i++) {
			//-1000<=nums[i]<=1000
			if (nums[i] == 1001)
				continue;
			int c = i;
			if (isLoop(c, nums)) {
				nums[c] = 1001;
				return true;
			}
			nums[c] = 1001;
		}
		return false;
	}

	private boolean isLoop(int c, int[] nums) {
		int len = nums.length;
		int next = (c + (nums[c] % len) + len) % len;
		if (nums[next] == 1002) {
			return true;
		}
		if (nums[next] == 1001 || c == next || nums[c] * nums[next] < 0) {
			return false;
		}
		nums[c] = 1002;
		
		if (isLoop(next, nums)) {
			nums[next] = 1001;
			return true;
		} else {
			nums[next] = 1001;
			return false;
		}
	}

3、源代码(不用递归)

递归太耗时，且递归+三色法每次要修改nums[next] = 1001;

public boolean circularArrayLoop(int[] nums) {
		/*
		 * 分析问题 按照游戏规则，nums自己的下标+自己的数=nums下一个下标。 通过节点是否走过来循环，通过取余去循环向前走，走过的节点都记录一下。
		 * 判断前方是否与自己异号，若异号，则重新游走。若前方是已访问节点，则重新游走。 用list把当前走过的节点记录起来，当走到list里的节点。
		 * 判断此下标是不是当前下标，若是，continue;若不是，则返回true.
		 */
		int len = nums.length;
		for (int i = 0; i < len; i++) {
			if (nums[i] < 1001){
			int c = i,next=i;
            while(true){
                c = next; 
                next = (c+(nums[c]%len)+len)%len;
                if(nums[next] == 1001+i){ 
                     return true;
                } 
                //如果nums[next] == 1001+i就return，所以在这可以简单判断1000 < nums[c]，c==next的机会比异号少，把异号排前面
                if(1000 < nums[c] || nums[c] * nums[next] <0  || c==next)
                      break;
                nums[c] = 1001+i;
                
            }
			
		}
        }
		return false;
      
	}