双指针算法专题

一、不修改数组找出重复的数字

给定一个长度为n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。

请找出数组中任意一个重复的数，但不能修改输入的数组。

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

思考题：如果只能使用 O(1) 的额外空间，该怎么做呢？

//我的第一反应是一般看到重复什么的，我就会下意识的想到hash，于是我就写了一种数组hash的方法

class Solution {
public:
    int duplicateInArray(vector& nums) {
        int vim[1000010] = {0} ;
        int n = nums.size() ;
        for(int i =  0 ; i < n ;++i)
        {
            vim[nums[i]] ++ ;
            if(vim[nums[i]] > 1 )
                return nums[i] ;
        }
        return 0 ;
    }
};
//这样时间复杂度是o(n) ,空间复杂度是o(n)

然后我又看到了有大佬用模拟链表来做，觉得是很有意思的思路。于是学习了.

class Solution {
public:
    int duplicateInArray(vector& nums) {
        int slow = 0 , fast = 0 ;
        
        do
        {
            fast = nums[nums[fast]] ;
            slow = nums[slow] ;
        }while(slow != fast) ;
    
        fast = 0 ;
        
        do
        {
            fast = nums[fast] ; 
            slow = nums[slow] ;
        }while(fast != slow) ;
   return slow ;
    }
};

时间复杂度是o(n) ,空间复杂度是o(1) 。

妙在用数组模拟链表的思路：

基于是链表找环的问题，题目是这样的

剑指 Offer II 022. 链表中环的入口节点 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL || head->next == NULL) return NULL ;
        ListNode* fast = head->next->next ;
        ListNode* slow = head->next ;
        while(fast && fast->next )
        {
            fast = fast->next->next ;
            slow = slow->next ;
            if(slow == fast) 
            break ;
        }
        if(slow != fast) return NULL ;
        else fast  = head ;

        while(slow != fast)
        {
            slow = slow->next ;
            fast = fast->next ;
        }
        return fast ;
    }
};

大佬采用的是用数组下标映射值的方法，因为本题正好下标的范围其实在0-n，值的范围在1-n，也就是说存在可以相互映射的可能。

把数组全部转换成链表之后是

2->5->2 然后就是死循环了。