circular-array-loop（蛮难的）

https://leetcode.com/problems/circular-array-loop/

题目蛮难的，有一些坑。

前后两个指针追赶找环的方法，基本可以归结为一种定式。可以多总结。

package com.company;


class Solution {
    // 参考了这里的解法
    // https://discuss.leetcode.com/topic/66894/java-slow-fast-pointer-solution
    public boolean circularArrayLoop(int[] nums) {
        for (int i=0; i<nums.length; i++) {
            if (nums[i] == 0) {
                continue;
            }
            int j = i, k = getIndex(i, nums);
            // 检查同方向
            while (nums[i] * nums[k] > 0 && nums[i] * nums[getIndex(k, nums)] > 0) {
                if (j == k) {
                    // 碰到了
                    // 检查是否只有一个元素
                    if (j == getIndex(j, nums)) {
                        break;
                    }
                    return true;
                }
                // 一前一后两个指针
                j = getIndex(j, nums);
                k = getIndex(getIndex(k, nums), nums);
            }
            // 把已经走过的,置为0
            j = i;
            k = nums[j];
            // 但要注意不同方向的不要置为0
            while (nums[j]*k > 0) {
                int tmp = getIndex(j, nums);
                nums[j] = 0;
                j = tmp;
            }
        }
        return false;
    }

    // 下面这个函数也是参考了上面Discuss里面的解法
    private int getIndex(int i, int[] nums) {
        int n = nums.length;
        int j = (i + nums[i]) >= 0 ? (i + nums[i]) % n : n + ((i + nums[i]) % n);
        return j;
    }
}

public class Main {

    public static void main(String[] args) throws InterruptedException {

        System.out.println("Hello!");
        Solution solution = new Solution();

        // Your Codec object will be instantiated and called as such:
        int[] nums = {2, -1, 1, -2, -2};
        boolean ret = solution.circularArrayLoop(nums);
        System.out.printf("ret:%b
", ret);

        System.out.println();

    }

}