algo-aha

数组中找重复值

• https://leetcode.com/problems/find-the-duplicate-number/

int findDuplicate(vector<int>& nums) {
    // 由鸽笼原理，一定有重复
    // 把nums[i]看做下标i的next下标，相当于链表的next指针，
    // 找重复的数变成链表中找环的入口点，快慢指针法
    int fast = 0, slow = 0;
    while (true) {
        fast = nums[nums[fast]];
        slow = nums[slow];
        if (fast == slow) break;
    }
    fast = 0;
    while (fast != slow) {
        fast = nums[fast];
        slow = nums[slow];    
    }
    return fast;
}

循环数组中找单向循环

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

快慢指针找循环，将够不成循环的路径上的点都设为0。

bool circularArrayLoop(vector<int>& nums) {
    const int N = nums.size();
    // 快慢指针找循环
    for (int i = 0; i < N; i++) {
        if (nums[i] == 0) continue; // 无循环路径上的点已设为0

        // 看从i出发是否构成单向循环
        int fast = i, slow = i;
        while (true) {
            int next = getNext(fast, nums);
            if (nums[i] * nums[next] < 0) break; // 循环方向变了
            fast = next, next = getNext(fast, nums);
            if (nums[i] * nums[next] < 0) break;
            fast = next;
            
            slow = getNext(slow, nums);
            if (fast == slow) { // 有环
                if (getNext(fast, nums) == fast) break; // 循环长度==1
                return true;
            }
        }
        
        // 至此从i出发够不成循环，将路径上的点都设为0
        int sign = nums[i], curr = i;
        while (sign * nums[curr] > 0) {
            int next = getNext(curr, nums);
            nums[curr] = 0;
            curr = next;
        }
    }
    return false;
}

int getNext(int idx, vector<int> &nums) {
    const int N = nums.size();
    int ans = (idx + nums[idx]) % N;
    if (ans < 0) ans += N;
    return ans;
}

更多快慢指针的例子见链表