智商欠费，死活想不出来

能帮忙看看这套题吗287. Find the Duplicate Number
想不出来，看了别人的答案，发现是要通过检测环来看那唯一重复的数，套路代码是：
class Solution {
    public int findDuplicate(int[] nums) {
       。。。边界检查。。。        
        int i = nums[0];
        int j = nums[nums[0]];
        while(i != j){
             i = nums[i];
             j = nums[nums[j]];
        }


        j = 0;        
        while(i != j){
            i = nums[i];
            j = nums[j];
        }
        return i;
    }
}
------------可是给了答案，我还是糊涂了-----------
我在第一个循环那卡主了        
        int i = nums[0];
        int j = nums[nums[0]];
        while(i != j){
             i = nums[i];
             j = nums[nums[j]];
        }
如果我的 test case 是 [3,2,1,4,5,4]， 我自己用笔画下来是死循环啊，永远不会相等，但是代码跑起来又没有问题。
i = 3->4->5->4->5->4
j = 4->5->4->5->4->5
但是实际运行打印出来的是:
i = 3 ->4
j= 4 -> 4

想很久也想不明白，我到底哪一步画错了呢

nt2701 发表于 2023-2-6 14:46
不是的lz，你看错了j的value，按照你的test case [3,2,1,4,5,4]来。
那么 j = nums[nums[0] = 3] = 4-> nu ...

还真是。糊涂了。看着代码都能想错。
谢谢你指出来。

想不出来很正常的，这题本质上是道linked list题。建议直接看题解或者视频。

一个很重要的点就是list里面的数字是从1 - n，然后list长度是n+1。你拿value去当index的时候永远不会越界。

这种是属于做过就知道怎么做，没做过的话除了出题人90%都做不出来的。

俺用的 JavaScript 写的。


/**
* @param {number[]} nums
* @return {number}
*/
var findDuplicate = function(nums) {
    const map = new Map();

    for(let i = 0, len = nums.length;i<len; i++) {
        let num = nums[i];

        if(map.has(num)) {
            return num;
        } else {
            map.set(num, i)
        }
    }
}

俺发现俺的 毛病就是总觉得自己写的有毛病，循环一遍会不会太差，结果发现好多次就是俺想复杂了。

看起来你的思路很混乱，你有了解过快慢指针模板吗？

我在上班没办法access ppt， 晚上可以给你贴一个

谢谢。
linkedlist那道环的题我是做的滚花烂俗了，那套题起码看着还知道相遇节点在哪里。可是这里，值和index互相交换，看了答案，还是不明白怎么回事。自己搞一搞例子，结果还是不明白。

嗯，放弃了。准备就背着，真遇到了直接默写代码。

红A 发表于 2023-2-6 13:02
看起来你的思路很混乱，你有了解过快慢指针模板吗？

我在上班没办法access ppt， 晚上可以给你贴一个

快慢指针我很熟啊，在给定范围比如圈，走一步和走两步的一定会相遇。但是这里，为啥index和值可以不停交换呢？ 而且我发现如果值范围是0-n-1，然后n+1个数的数组，第一个数是0的话，那这套代码就是死循环。

红A 发表于 2023-2-6 13:02
看起来你的思路很混乱，你有了解过快慢指针模板吗？

我在上班没办法access ppt， 晚上可以给你贴一个

谢谢，期待你的ppt

另外初始化如果我是你，我会选择i= 0， j = nums[0], 不要一口气跳很多步
应该是初始化之后，你的j一次跳了4步，i走了2步

红A 发表于 2023-2-6 13:04
另外初始化如果我是你，我会选择i= 0， j = nums[0], 不要一口气跳很多步
应该是初始化之后，你的j一次跳 ...

跳多少步不是取决于值的大小嘛？

跳一步的意思是把当前value当做index，跳两部一次是value -> index == value -> index 和值的大小无关，是一次value->index转化算一步