457. 环形数组是否存在循环
思路：与141. 环形链表题类似，
因为可以将环形数组理解为图中的 nn 个点，nums[i]nums[i] 表示 ii 号点向 (i + nums[i]) mod n 号点连有一条单向边。注意到这张图中的每个点有且仅有一条出边，这样我们从某一个点出发，沿着单向边不断移动，最终必然会进入一个环中。而依据题目要求，我们要检查图中是否存在一个所有单向边方向一致的环。我们可以使用在无向图中找环的一个经典算法：快慢指针 来解决本题
ps: 我用了哈希表存储了下一步，答案中用了next function 来取下一步：
<![CDATA[
class Solution {
public boolean circularArrayLoop(int[] nums) {
int N = nums.length;
Map<Integer, Integer> hm = new HashMap<Integer, Integer>();
for(int i=0; i<N; i++){
hm.put(i, ((i+nums[i])%N+N)%N);
}
// System.out.println(hm.toString());
for(int i=0; i<N; i++){
int slow = i;
int fast = hm.get(slow);
while(nums[slow]*nums[fast]>0 && nums[slow]*nums[hm.get(fast)]>0){
// System.out.println(slow+" "+fast+" "+nums[slow]+" "+nums[fast]);
if(slow==fast){
// k>1
if(slow == hm.get(slow)) break;
else return true;
}
slow = hm.get(slow);
// System.out.println(hm.get(fast));
fast = hm.get(hm.get(fast));
}
// 标记已经遍历过的节点：
int add = i;
while (nums[add] * nums[hm.get(add)] > 0) {
int tmp = add;
add = hm.get(add);
nums[tmp] = 0;
}
}
return false;
}
}
// class Solution {
// public boolean circularArrayLoop(int[] nums) {
// int n = nums.length;
// for (int i = 0; i < n; i++) {
// if (nums[i] == 0) {
// continue;
// }
// int slow = i, fast = next(nums, i);
// // 判断非零且方向相同
// while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[next(nums, fast)] > 0) {
// if (slow == fast) {
// if (slow != next(nums, slow)) {
// return true;
// } else {
// break;
// }
// }
// slow = next(nums, slow);
// fast = next(nums, next(nums, fast));
// }
// int add = i;
// while (nums[add] * nums[next(nums, add)] > 0) {
// int tmp = add;
// add = next(nums, add);
// nums[tmp] = 0;
// }
// }
// return false;
// }
// public int next(int[] nums, int cur) {
// int n = nums.length;
// return ((cur + nums[cur]) % n + n) % n; // 保证返回值在 [0,n) 中
// }
// }
// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/circular-array-loop/solution/huan-xing-shu-zu-shi-fou-cun-zai-xun-hua-0ay2/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
]]>
