287. Find the Duplicate Number - Medium

前往題目

想法

• 毫無想法，因為不能動array，然後一定要constant time

思路

這題連neetcode大大都說討厭，這是我第一次聽到他說不喜歡題目🤣總之就是一個沒看過的人根本就幾乎不可能30分鐘內想出來的問題

1. Linked List cycle
2. 快慢指針
3. Floyd's algo.

Code

這題背就對了

詳細解釋可以看Neetcode大大的影片或是討論區

class Solution {
    public int findDuplicate(int[] nums) {
        // Floyd's algo.

        // Init. pointers at the beginning
        int slow = 0, fast = 0;

        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }

        int slow2 = 0;

        // Move 1 step until meet
        // by mathematics
        while(true) {
            slow = nums[slow];
            slow2 = nums[slow2];
            if (slow == slow2) break;
        }

        return slow;
    }
}

2024/04/23

• 背誦題😂